傳送門

見計數想容斥

顯然每個人交換后可以變成任意的排列

所以就是求對于所有排列使得每個位置的值都和一開始的值不同

感覺同一個值算同一個數不太好搞，考慮把所有數都看成不同的，最后答案再除 $\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的喜糖的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。