首页 > 代码库 > BZOJ4714 : 旋转排列
BZOJ4714 : 旋转排列
对于每个$k$，问题等价于求有多少置换满足：
1.存在一个循环长度为$k$
2.任意一个循环长度$\geq 2$
枚举这种环的个数$t$：
设$g_t$表示至少有$kt$个人分成$t$个长度为$k$的循环的方案数，考虑枚举第一个人和哪些人分在了一起，同时有$(k-1)!$种可能的环，有$g_t=C(kt-1,k-1)g_{t-1}(k-1)!$。
设$d_i$表示$i$个人错位排列的方案数，那么至少有$t$个长度为$k$的循环的方案数为$C(n,kt)g_td_{n-kt}$。
考虑容斥，则这部分对答案的贡献为$(-1)^{t-1}C(n,kt)g_td_{n-kt}$。
时间复杂度$O(n\log n)$。
#include<cstdio>const int N=500010,P=1000000007;int n,i,j,k,t,f[N],inv[N],d[N],g[N],ans;int main(){ scanf("%d",&n); for(f[0]=i=1;i<=n;i++)f[i]=1LL*f[i-1]*i%P; for(inv[0]=inv[1]=1,i=2;i<=n;i++)inv[i]=1LL*(P-inv[P%i])*(P/i)%P; for(i=1;i<=n;i++)inv[i]=1LL*inv[i-1]*inv[i]%P; for(d[0]=d[2]=1,i=3;i<=n;i++)d[i]=1LL*(i-1)*(d[i-2]+d[i-1])%P; for(i=0;i<=n;i++)d[i]=1LL*d[i]*inv[i]%P; for(g[0]=1,i=2;i<=n;i++)for(j=1,k=i;k<=n;j++,k+=i){ g[j]=1LL*g[j-1]*f[k-1]%P*inv[k-i]%P; t=1LL*inv[k]*d[n-k]%P*g[j]%P; if(j&1){ ans+=t; if(ans>=P)ans-=P; }else{ ans-=t; if(ans<0)ans+=P; } } ans=1LL*ans*f[n]%P; return printf("%d",ans),0;}
BZOJ4714 : 旋转排列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。