这场BC实在是有趣啊,T2是个没有什么算法但是细节坑的贪心+分类讨论乱搞,T3反而码起来很顺. 然后出现了T2过的人没有T3多的现象(T2:20人,T3:30人),而且T2的AC率是惨烈的不到3% (我T2读入写挂,思路想挂,推倒重码一次,交了7次才过QAQ) 最后狂码T3赶在结束之前调出来过了,3题最后都没有被叉也没有fst,捡了个rk9,人品好啊.
给出26个字母的一个排列,对一个字符串进行一次变换表示将某个字母变成排列中对应的字母. 例如zabcdefg....wxy,1表示经过一次变换之后,所有的'a'会变成'z','b'会变成'a','c'会变成'b'... 一个长度为N的随机串经过若干次变换之后必然得到本身.那么我们可以求出得到本身的最小变换次数. 长度为N的串有\(26^N\)个,求这些串的最小变换次数之和.\(N<=10^9\)
给出的置换中,对于某一个字母,它至少变换多少次之后得到自身是已知的.对于某一个随机串,它变换到 自己的最小步数只和出现过的字母种类有关,对出现过的字母变换到自身的最小步数求lcm即可.那么我们 对出现过的字母种类进行状压,用\(f[i][S]\)表示前i个字母中出现的字母集合为S的方案数.那么\(f[i-1][]\) 到\(f[i][]\)的转移是可以看作矩阵乘法形式的,于是我们可以在\(2^{26}logN\)的时间内解决暴力. 仔细分析.如果某个字母变换到自己的最小次数是3,那么它位于一个长度为3的循环中,这3种字母变换到自己 的最小步数是相同的,因此可以在状态压缩的时候视为一种.如果两个字母处在不同的循环但是长度相同,例如 "badc....",'a,'b','c','d'的最小步数均为2,也可以视为一种.那么长度为26的串里最多出现6种不同的 循环长度,我们就可以在\(O(2^6logN)\)内解决.也可以dfs枚举出所有可行的lcm,数量不会比2^6多.
#include<cstdio> #include<cstring> #include<algorithm> #include<map> using namespace std; const int mod=1000000007; int sz; struct matrix{ int a[130][130]; matrix(){ memset(a,0,sizeof(a)); } matrix(int x){ memset(a,0,sizeof(a)); for(int i=0;i<130;++i){ a[i][i]=x; } } matrix operator *(const matrix &B)const{ matrix C; for(int i=1;i<=sz;++i){ for(int j=1;j<=sz;++j){ for(int k=1;k<=sz;++k){ C.a[i][k]=(C.a[i][k]+a[i][j]*1ll*B.a[j][k])%mod; } } } return C; } }; matrix qpow(matrix A,int x){ matrix ans(1); for(;x;x>>=1,A=A*A){ if(x&1)ans=ans*A; } return ans; } char buf[30]; int a[30]; int vis[30],T; int w[30]; int b[30];int tot=0; int lcm[1024];int totlcm=0; int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } int LCM(int a,int b){ return a/gcd(a,b)*b; } void dfs(int x,int tmp){ if(x==tot+1){ lcm[++totlcm]=tmp; return; }else{ dfs(x+1,tmp); dfs(x+1,LCM(tmp,b[x])); } } matrix A,ANS; int main(){ int tests;scanf("%d",&tests); while(tests--){ tot=0; int n;scanf("%d",&n); scanf("%s",buf+1); for(int i=1;i<=26;++i){ a[i]=buf[i]-'a'+1; } ++T; for(int i=1;i<=26;++i){ if(vis[i]!=T){ int cnt=0; for(int j=i;vis[j]!=T;j=a[j]){ cnt++;vis[j]=T; } b[++tot]=cnt; w[i]=cnt; for(int j=a[i];j!=i;j=a[j]){ w[j]=cnt; } } } sort(b+1,b+tot+1); int sum=0; for(int i=1;i<=tot;++i){ if(b[i]!=b[i-1]){ b[++sum]=b[i]; } } tot=sum; totlcm=0; dfs(1,1); sort(lcm+1,lcm+totlcm+1); sum=0; for(int i=1;i<=totlcm;++i){ if(lcm[i]!=lcm[i-1])lcm[++sum]=lcm[i]; } totlcm=sum; A=matrix(0); map<int,int> dict; for(int i=1;i<=totlcm;++i)dict[lcm[i]]=i; for(int i=1;i<=totlcm;++i){ for(int j=1;j<=26;++j){ A.a[i][dict[LCM(lcm[i],w[j])]]++;//printf("%d %d\n",i,dict[LCM(lcm[i],w[j])]); } }sz=totlcm; ANS=qpow(A,n); int ans=0; for(int i=1;i<=totlcm;++i){ ans=(ans+lcm[i]*1ll*ANS.a[1][i])%mod; } printf("%d\n",ans); // for(int i=1;i<=totlcm;++i)printf("%d ",lcm[i]);printf("\n"); // for(int i=1;i<=tot;++i)printf("%d ",b[i]);printf("\n"); } return 0; }转载于:https://www.cnblogs.com/liu-runda/p/6660917.html
相关资源：数据结构—成绩单生成器