本文共 1911 字，大约阅读时间需要 6 分钟。
这道题就是深搜矩阵，再快速幂。
1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 const int maxn=200; 7 const int mod=65521; 8 struct Matrix{ 9 long long mat[maxn][maxn]; 10 int r,c; 11 Matrix(int r_=0,int c_=0,int on=0){ 12 memset(mat,0,sizeof(mat)); 13 r=r_;c=c_; 14 if(on)for(int i=1;i<=r;i++)mat[i][i]=1; 15 } 16 Matrix operator *(Matrix a){ 17 Matrix ret(r,a.c); 18 long long l; 19 for(int i=1;i<=r;i++) 20 for(int k=1;k<=c;k++){ 21 l=mat[i][k]; 22 for(int j=1;j<=a.c;j++) 23 (ret.mat[i][j]+=(l*a.mat[k][j])%mod)%=mod; 24 } 25 return ret; 26 } 27 Matrix operator ^(long long k){ 28 Matrix ret(r,c,1),x(r,c); 29 for(int i=1;i<=r;i++) 30 for(int j=1;j<=c;j++) 31 x.mat[i][j]=mat[i][j]; 32 while(k){ 33 if(k&1) 34 ret=ret*x; 35 k>>=1; 36 x=x*x; 37 } 38 return ret; 39 } 40 }A,B; 41 42 long long n; 43 map ID; 44 map used; 45 int k,e,e1,E[maxn][2]; 46 int cnt,st[1<<17],mem[1<<17]; 47 int fa[maxn],sz[maxn],vis[maxn]; 48 int Find(int x){ 49 return x==fa[x]?x:fa[x]=Find(fa[x]); 50 } 51 bool Check(int s){ 52 for(int i=1;i =0;s--) 71 if(Check(s)){ 72 memset(vis,0,sizeof(vis));num=0; 73 for(int i=1;i<=x;i++){ 74 if(vis[Find(i)])continue; 75 vis[Find(i)]=++num; 76 } 77 num=0; 78 for(int i=1;i<=x;i++) 79 num=num*10+vis[Find(i)]; 80 if(ID[num])B.mat[ID[num]][1]+=1; 81 else{ 82 A.r+=1;A.c+=1;B.r+=1; 83 B.mat[ID[num]=B.r][1]=1; 84 st[++cnt]=s;mem[cnt]=num; 85 } 86 } 87 88 for(int t=1,s;t<=cnt;t++){ 89 for(int p=(1< =0;p--){ 90 s=st[t]^(p<
转载于:https://www.cnblogs.com/TenderRun/p/5568906.html
