BZOJ4665 小 w 的喜糖

這道題可以說是二項式反演的經典應用。

第一次轉化，題目中說使每個人手里的糖都不相同，類似于錯排問題，而我們顯然是不好直接進行處理的。于是考慮轉化為計算使一部分人手里的糖與原來相同的方案數，如果記作 \(g(i)\)，那么答案就是 \(g(0)\)。

第二次轉化，看到恰好，于是用二項式反演轉化為求欽定。記欽定的方案為 \(f(i)\)，則二項式反演的公式為

既然我們只需要求出 \(g(0)\)，那么根據上述公式，就有

考慮如何求出 \(f(0),f(1),\dots,f(n)\)。不妨用 DP 來求解，設 \(\mathit{dp}(i,j)\) 表示枚舉到第 \(i\) 種喜糖，欽定 \(j\) 個人拿到的糖和原來相同的方案數。發現同種喜糖是相同的，而這一限制比較麻煩，不妨認為所有喜糖都是互不相同的，而我們只需在最后給答案乘上 \(\prod1/c_i!\) 即可，其中 \(c_i\) 是第 \(i\) 種喜糖的數量。這樣我們就暫時不用考慮去重問題，有轉移方程

簡單來說就是枚舉在所有欽定的人中，有多少人的糖在當前種類里，即 \(k\)。那么我們首先要從原來就是這種糖的人中選出 \(k\) 個人，然后再挑出 \(k\) 個糖按順序放在這些人手上。所以會先乘排列數然后乘組合數。

邊界條件顯然是 \(\mathit{dp}(0,0)=1\)。這樣算下來之后，我們的 \(f(i)\) 實際上是 \(\mathit{dp}(m,i)\times(n-i)!\)，因為 \(\mathit{dp}(i,j)\) 的轉移方程里只計算了欽定的方案數，而沒有計算欽定以外的人隨意排列的方案數。

那么現在我們有了 \(f(i)\)，就能算出 \(g(0)\)，然后再乘上 \(\prod1/c_i!\)，這個題就做完了。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
constexpr int MAXN=2005;
constexpr ll MOD=1e9+9;
int n,c[MAXN],m;
ll fac[MAXN],inv[MAXN];
ll f[MAXN][MAXN];
ll power(ll a,ll b){
    ll res=1;
    for(;b;a=a*a%MOD,b>>=1)if(b&1)res=res*a%MOD;
    return res;
}
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
	inv[n]=power(fac[n],MOD-2);
	for(int i=n-1;~i;i--) inv[i]=inv[i+1]*(i+1)%MOD;
}
ll C(int n,int m){
	if(n<m) return 0;
	return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
ll A(int n,int m){
	if(n<m) return 0;
	return fac[n]*inv[n-m]%MOD;
}

int main(){
	cin.tie(nullptr)->sync_with_stdio(0);
	cin>>n;
	init(n);
	for(int i=1,x;i<=n;i++) cin>>x,c[x]++,m=max(m,x);
	f[0][0]=1;
	for(int i=1,pre=c[1];i<=m;i++,pre+=c[i])
		for(int j=0;j<=pre;j++)
			for(int k=0;k<=min(j,c[i]);k++)
				f[i][j]=(f[i][j]+f[i-1][j-k]*C(c[i],k)%MOD*A(c[i],k))%MOD;
	ll ans=0;
	for(int i=0;i<=n;i++) ans=(ans+f[m][i]*fac[n-i]*(i&1?-1:1))%MOD;
	for(int i=1;i<=m;i++) ans=ans*inv[c[i]]%MOD;
	cout<<(ans+MOD)%MOD<<'\n';
	return 0;
}