我有點懵逼瞎容斥就過了

首先看了下路牌就是容斥

明顯位置沒有用，排一波序把拿相同顏色的球的人放一起

設f[i][j]表示枚舉到第i個顏色，至少j個人拿了和原來一樣顏色的球

那么f[i+1][j+k]=(f[i+1][j+k]+f[i][j]*C[p[i+1]][k]%mod*C[(ls+p[i+1])-(j+k)][p[i+1]-k])%mod;

p是當前球數，ls是前面球數的和，加起來相當于當前總球數

C[p[i+1]][k]是選k個人拿和原來一樣顏色的球，C[(ls+p[i+1])-(j+k)][p[i+1]-k]是在剩下的位置中把沒有拿的球找個位置放好

考慮這里的容斥系數，也就是對于重復人數為d的一個方案，對f[n][k]的貢獻次數

開始我想成了每個不同顏色的球的組合數加起來剛好等于k，實際上可以合并起來看，在d個球中選出k個已確定，就是C[d][k]

那么上二項式反演即可

由于C[i][0]=1，網上很多人都說系數就是1，直接+1-1...................

容斥的時候輸出答案記得要(ans+mod)%mod啊，系數有-1的啊！！！！！！！！！！！！！！！！

#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const int _=1e2; const int maxn=2*1e3+_; const int maxm=2*1e3+_; const LL mod=1e9+9; LL C[maxn][maxn]; void yu() {C[0][0]=1;for(int i=1;i<maxn;i++){C[i][0]=1;for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;} }int a[maxn],m,p[maxm]; LL f[maxm][maxn];//前i個數中，相同個數至少為j的個數 int main() {freopen("a.in","r",stdin);freopen("a.out","w",stdout);yu();int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1);m=1,p[1]=1;for(int i=2;i<=n;i++){if(a[i]!=a[i-1])m++;p[m]++;}int ls=0; f[0][0]=1;for(int i=0;i<m;i++){for(int j=0;j<=ls;j++)if(f[i][j]){for(int k=0;k<=p[i+1];k++)f[i+1][j+k]=(f[i+1][j+k]+f[i][j]*C[p[i+1]][k]%mod*C[(ls+p[i+1])-(j+k)][p[i+1]-k])%mod;}ls+=p[i+1];}LL ans=0;int u=1;for(int i=0;i<=n;i++){ans=(ans+u*C[i][0]*f[m][i])%mod;u=-u;}printf("%lld\n",(ans+mod)%mod);return 0; }

?

轉載于:https://www.cnblogs.com/AKCqhzdy/p/10442237.html

總結

以上是生活随笔為你收集整理的bzoj4665: 小w的喜糖的全部內容，希望文章能夠幫你解決所遇到的問題。

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