MG loves string
Accepts: 30Submissions: 67Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 262144/262144 K (Java/Others)问题描述MG是一个很忙碌的男孩子。今天他沉迷于这样一个问题： 对于一个长度为N的由小写英文字母构成的随机字符串，当它进行一次变换，所有字符i都会变成a[i]。 MG规定所有a[i]构成了26个字母组成的排列。 MG现在需要知道这个随机串变换到自身的期望变换次数。请你输出期望答案乘上26^n以后模 1000000007的结果。 MG认为这件事非常容易，不屑于用计算机解决，于是运用他高超的人类智慧开始进行计算。作为一名旁观者，你也想挑战MG智慧，请你写个程序，计算答案。输入描述第一行一个整数T，代表数据组数（1 <=T<=10）。 接下来，对于每组数据—— 第一行一个整数N，表示给定的随机串长度（1<=N<=1000000000）。 第二行26个字母，表示a_i序列输出描述对于每一组数据，输出一行。 显然，这个期望是一个实数。请你输出它乘上26^N以后模 1000000007 的结果输入样例2
2
abcdefghijklmnpqrstuvwxyzo
1
abcdefghijklmnopqrstuvwxyz输出样例5956
26
【分析】
感觉BC的题挺好的啊【每次都能学到东西。。
首先，知道，这是个带LCM的期望。就是看随机串分别在长度为几的循环节里面，然后LCM。
然后，不同长度的循环节不会超过6个，1+2+3+4+5+6=21。
就是根据输入的那个串，只会有6种长度的循环节，所以你可以枚举真正的随机串涵盖的循环节有哪几个，枚举是2^6。
然后就是把n个字符放到那些循环节的字母集合中去，但是要保证每个循环节都一定有一个字母覆盖，问它的方案数。
其实这是经典的容斥原理，就是n个东西分到m个集合，让每个集合都至少有一个东西。
这里我们枚举子集就可以用容斥原理计算出来了【注意容斥，你要减掉的是没有涵盖某一个集合的，加上没有涵盖两个集合的。。。】
枚举子集是3^n（用二项式定理易证）
这个可以预处理的。
所以是$O(2^6*\log(n)+3^6)$
官方题解：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Mod 1000000007
#define LL long long int u[],v[],pp[],n;
LL sm[];
int h[],ss[],p[];
char s[];
bool vis[]; LL qpow(LL x,int b)
{
x%=Mod;
LL ans=;
while(b)
{
if(b&) ans=(ans*x)%Mod;
x=(x*x)%Mod;
b>>=;
}
return ans;
} void init()
{
memset(vis,,sizeof(vis));
memset(p,,sizeof(p));
memset(h,,sizeof(h));
memset(ss,,sizeof(ss));
scanf("%d",&n);
scanf("%s",s+);
for(int i=;i<=;i++) u[i]=s[i]-'a'+;
for(int i=;i<=;i++) if(!vis[i])
{
vis[i]=;
int x=i,cnt=;
while(u[x]!=i) x=u[x],cnt++,vis[x]=;
p[cnt]++;
}
v[]=;
for(int i=;i<=;i++) if(p[i]) v[++v[]]=i,pp[v[]]=p[i];
for(int i=;i<(<<v[]);i++)
for(int j=;j<=;j++) if(i&(<<j-)) ss[i]+=v[j]*pp[j],h[i]++;
for(int i=;i<(<<v[]);i++) sm[i]=qpow(ss[i],n);sm[]=;
int i;
// for(i=0;i<(1<<v[0]);i++)
for(i=(<<v[])-;i>=;i--)
for(int j=i;j;j=(j-)&i)
{
if(i==j) continue;
if((h[i]-h[j])%==) sm[i]+=sm[j];
else sm[i]-=sm[j];
sm[i]=(sm[i]%Mod+Mod)%Mod;
}
} LL gcd(LL a,LL b)
{
if(b==) return a;
return gcd(b,a%b);
} LL ans; void ffind(int x,int y,LL nw)
{
if(x==v[]+)
{
ans=(ans+sm[y]*nw)%Mod;
return;
}
ffind(x+,y,nw);
ffind(x+,y|(<<x-),nw*(LL)v[x]/gcd(nw,v[x]));
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
init();
ans=;ffind(,,);
printf("%lld\n",ans);
}
return ;
}
2017-04-02 10:41:18