(相关资料图)
题目链接
首先明确概念：
- 排列。指的就是一个把数组a重排得到的序列，两个排列相等当且仅当它们对应位全都相等
- 环形排列。指的是把数组a重排得到的序列首尾相接得到的环形数组，两个环形排列相等当且仅当它们通过位移能够变得对应位全部相等
这题其实是要对所有不同的环形排列，求其中连续相同的数构成的连通块个数的期望值。特判a中数全相同的情况，其余情况其实只要求出相邻两个数不同的位置个数的期望值就行了，把这个期望值称为一个环形排列的"权值"。一个排列的权值指的是把它视为环形排列之后的权值(1,n也算相邻)。对于一个排列p，有多少个与它不同的排列在作为循环排列时与它相同？其实这与p的最短循环节长度有关，令这个长度为\(len\)。这里的循环节必须是完整的，也就是\(|p|\ mod \ len=0\)，且把\(p\)平均切成\(\frac{|p|}{len}\)段之后每段都相同。观察发现对于p，有\(len-1\)个与它不同的排列在作为循环排列时与它相同，也就是等价类大小为\(len\)。如果能对每个\(len\)求出所有最小循环节大小为\(len\)的不同排列的权值和\(f_{len}\)与总个数\(cnt_{len}\)，那么题目要求的答案就是\(\frac xy\)，其中\(x=\sum_{len|n}\frac{f_{len}}{len},y=\sum_{len|n}\frac{cnt_{len}}{len}\)。
令\(a\)中数\(i\)出现的次数为\(b_i\)。现在枚举\(len\)，尝试计算出\(f_{len}与cnt_{len}\)。令\(B=\frac n{len}\)，显然对于任意i，必须满足\(B|b_i\)，否则就不存在最短循环节为len的排列。然后想到用容斥，先计算出实际最小循环节长度为\(len\)的约数的排列的权值和与总个数。令\(b"_i=\frac{b_i}B\)。显然总个数为\(\frac{len!}{\prod{b"_i!}}\)。对于权值和，注意到整个排列被分成了\(B\)段，每一段都相等，所以可以把每一段都视为首尾相接的一个环形排列计算权值和，然后乘\(B\)。在每一段构成的小环形排列中，任意相邻两个位置贡献1的概率都相同，因为这个排列是随机的。这个概率的计算方法是先枚举靠前一个位置的值为\(i\)，其发生的概率为\(\frac{b"_i}{len}\)；后面一个位置的值必须与其不同，概率为\(\frac{len-b"_i}{len-1}\)。枚举所有的i，把这个概率相加即可。先暂时让\(f_{len}=\)此时算出的权值和，\(cnt_{len}=\)此时算出的总个数，然后进行这样一步容斥就能算出真正的\(f和cnt\)：
for(int i=1;i<=n;++i) for(int j=i+i;j<=n;j+=i) (f[j]+=MOD-f[i])%=MOD,(cnt[j]+=MOD-cnt[i])%=MOD;时间复杂度\(O(能过)\)。不知道怎么证明，但是看上去感觉不会被卡。
点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){ #ifdef LGS freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif}void termin(){ #ifdef LGS std::cout<<"\n\nEXECUTION TERMINATED"; #endif exit(0);}using namespace std;const LL MOD=998244353;LL qpow(LL x,LL a){LL res=x,ret=1;while(a>0){if(a&1) (ret*=res)%=MOD;a>>=1;(res*=res)%=MOD;}return ret;}LL t,n,a[1000010],b[1000010],f[1000010],cnt[1000010],fac[1000010],inv[1000010],rinv[1000010];vector v;void solve(LL len){ LL dv=n/len; rep(i,v.size()) v[i]/=dv; cnt[len]=fac[len];rep(i,v.size()) (cnt[len]*=inv[v[i]])%=MOD; LL possi=0,mul=rinv[len]*rinv[len-1]%MOD; rep(i,v.size()) (possi+=v[i]*(len-v[i])%MOD*mul)%=MOD; f[len]=possi*n%MOD*cnt[len]%MOD; rep(i,v.size()) v[i]*=dv;}int main(){ fileio(); fac[0]=1;repn(i,1000005) fac[i]=fac[i-1]*i%MOD; rep(i,1000003) inv[i]=qpow(fac[i],MOD-2),rinv[i]=qpow(i,MOD-2); cin>>t; rep(tn,t) { scanf("%lld",&n); rep(i,n+3) b[i]=f[i]=cnt[i]=0; rep(i,n) scanf("%d",&a[i]),++b[a[i]]; v.clear(); repn(i,n) if(b[i]) v.pb(b[i]); if(v.size()==1) { puts("1"); continue; } repn(len,n) if(n%len==0) { bool bad=false; LL dv=n/len; rep(i,v.size()) if(v[i]%dv!=0){bad=true;break;} if(bad) continue; solve(len); } //cout< 
