BZOJ 4665: 小w的喜糖

传送门

见计数想容斥

显然每个人交换后可以变成任意的排列

所以就是求对于所有排列使得每个位置的值都和一开始的值不同

感觉同一个值算同一个数不太好搞，考虑把所有数都看成不同的，最后答案再除 $\prod _{i=1}^{n}fac[cnt[i]]$（其中 $cnt[i]$ 表示值为 $i$ 的数的个数）

然后发现每个位置都要不同的限制很麻烦，考虑先求出 $F[i]$ 表示至少有 $i$ 个位置拿到原来的数的方案数

考虑 $dp$ 这个东西，设 $f[i][j]$ 表示已经选好值从 $1$ 到 $i$ 的数的位置，当前有 $j$ 个位置是原来的数，其他的位置还没考虑

那么考虑直接枚举这个值 $i$ 有 $k$ 个数还在原来的位置，$k \in [0,cnt[i]]$

那么有 $f[i][j]=\sum_{k=0}^{min(j,cnt[i])}f[i-1][j-k]C_{cnt[i]}^{k} (\prod_{p=cnt[i]-k+1}^{cnt[i]}p)$（就是我随便选出 $k$ 个位置，然后随便放在那 $cnt[i]$ 个位置上）

求出 $f[i][j]$ 以后那么 $F[i]=f[n][i]*(n-i)!$

然后容斥一下，$Ans=\sum_{i=0}^{n}(-1)^iF[i]$

别忘了最后要除一个 $\prod _{i=1}^{n}fac[cnt[i]]$

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }return x*f; } const int N=2007,mo=1e9+9; inline int fk(int x) { return x>=mo ? x-mo : x; } int n,m,A[N],cnt[N],Ans; int fac[N],inv[N],facinv[N],C[N][N],f[N][N]; int main() {n=read();for(int i=1;i<=n;i++) cnt[read()]++;fac[0]=1; inv[1]=1; facinv[0]=1;for(int i=1;i<=n;i++){fac[i]=1ll*fac[i-1]*i%mo;if(i!=1) inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo;facinv[i]=1ll*facinv[i-1]*inv[i]%mo;}C[0][0]=1;for(int i=0;i<=n;i++)for(int j=0;j<=i;j++){C[i+1][j]=fk(C[i+1][j]+C[i][j]);C[i+1][j+1]=fk(C[i+1][j+1]+C[i][j]);}f[0][0]=1;for(int i=1;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<=cnt[i]&&k<=j;k++)f[i][j]=fk( f[i][j]+ 1ll*f[i-1][j-k]*C[cnt[i]][k]%mo *fac[cnt[i]]%mo *facinv[cnt[i]-k]%mo );for(int i=0;i<=n;i++){if(i&1) Ans=fk(Ans+mo-1ll*f[n][i]*fac[n-i]%mo);else Ans=fk(Ans+1ll*f[n][i]*fac[n-i]%mo);}for(int i=1;i<=n;i++) Ans=1ll*Ans*facinv[cnt[i]]%mo;printf("%d",Ans);return 0; }

 

转载于:https://www.cnblogs.com/LLTYYC/p/10783442.html

总结

以上是生活随笔为你收集整理的BZOJ 4665: 小w的喜糖的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。