首先明确概念：
- 排列。指的就是一个把数组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 <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void 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 <LL> 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<<f[2]<<' '<<cnt[2]<<' '<<f[4]<<' '<<cnt[4]<<endl;
repn(i,n) for(int j=i+i;j<=n;j+=i) (f[j]+=MOD-f[i])%=MOD,(cnt[j]+=MOD-cnt[i])%=MOD;
LL up=0,dn=0;
repn(i,n) if(n%i==0) (up+=f[i]*qpow(i,MOD-2))%=MOD,(dn+=cnt[i]*qpow(i,MOD-2))%=MOD;
LL ans=up*qpow(dn,MOD-2)%MOD;
printf("%d\n",ans);
}
termin();
}