由于这一题数据很小，爆搜就行了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[15][15],h,w,ans=0;
set<int> s;
void dfs(int i,int j){
if(i>h||j>w) return;
if(s.find(a[i][j])!=s.end()) return;
if(i==h&&j==w) ans++;
s.insert(a[i][j]);
dfs(i+1,j);
dfs(i,j+1);
s.erase(a[i][j]);
}
signed main(){
cin>>h>>w;
for(int i=1;i<=h;++i){
for(int j=1;j<=w;++j){
cin>>a[i][j];
}
}
dfs(1,1);
cout<<ans;
return 0;
}
我们把单独的一条绳子也看成一条链，操作一次，就减少一条链，所以链的数量就等于 n-m 。
用并查集来判断两个绳子是否已经被链接，如果是，那就形成了一个环。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,f[N],ans1,ans2;
int fa(int x){
return f[x]==x?x:f[x]=fa(f[x]);
}
signed main(){
cin>>n>>m;
ans2=n-m;
int a,b;
char c;
for(int i=1;i<=n;++i) f[i]=i;
for(int i=1;i<=m;++i){
cin>>a>>c>>b>>c;
if(fa(a)==fa(b)){
ans1++;
}
else{
f[fa(a)]=fa(b);
}
}
cout<<ans1<<" "<<ans2;
return 0;
}
等比数列公式：
推导过程：
由于这里要模一个数，所以直接带走。
，我们可以让 先乘 ，然后就可以保证整除了。
ps:此处需要用到快速幂，并使用 __int128
#include<bits/stdc++.h>
#define int long long
#define _int __int128
using namespace std;
int a,x,mod,ans;
_int ksm(_int n,_int i,_int m){
if(i==0) return 1;
if(i==1) return n%m;
_int t=ksm(n,i/2,m)%m;
t=t*t%m;
if(i%2==1) t=t*n%m;
return t;
}
signed main(){
cin>>a>>x>>mod;
if(a==1){
cout<<x%mod;
return 0;
}
mod=mod*(a-1);
_int b=ksm(a,x,mod);
if(b==0) b=mod;
cout<<(int)((b-1)/(a-1));
return 0;
}