最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

Codeforces 1630 E Expected Components 题解 (组合数学)

来源：博客园


(相关资料图)

题目链接

首先明确概念：

  • 排列。指的就是一个把数组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<

关键词： 环形排列 当且仅当 循环排列