BZOJ 4710 [Jsoi2011]分特產 解題報告

4710 [Jsoi2011]分特產

題意

給定\(n\)個集合，每個集合有相同的\(a_i\)個元素，不同的集合的元素不同。將所有的元素分給\(m\)個不同位置，要求每個位置至少有一個元素，求分配方案數。

---

先考慮兩個簡單的問題

給定\(m\)個相同元素和\(n\)個不同位置，每個位置至少分一個的方案數？

使用插板法，等價于在\(m-1\)個空擋里插\(n-1\)個元素，方案數為

\[\binom{m-1}{n-1}\]

但是這樣考慮，這個題目是做不了的。

給定\(m\)個相同元素和\(n\)個不同位置，每個位置可以不分的方案數？

事實上還是插板，但可以一個位置插兩個板子。

把\(m\)個元素看做\(1\)，把\(n-1\)個插開點看做\(0\)，等價于從\(m+n-1\)個元素拿\(n-1\)個，方案數為

\[\binom{m+n-1}{n-1}\]

---

從問題\(2\)出發，我們就可以容斥了

把一種方案有幾個位置沒選作為方案的性質，我們可以計算出一個至少有幾個人沒選的方案集合的數量。

因為位置的計算方法是等價的，所以我們不需要枚舉子集，只需要簡單的按照組合數進行計算就可以了。

具體的說，我們把所有集合的元素都獨立按方案二的選出來，令\(f_i\)代表至少\(i\)個位置不選擇元素的方案數，則有

\[f_i=\binom{n}{i}\prod\limits_{j=1}^n \binom{a_j+n-i-1}{n-i-1}\]

則總方案是 至少\(0\)人-至少\(1\)人+...，即

\[\sum_{i=0}^{n-1}(-1)^if_i\]

---

Code:

#include <cstdio>
#define ll long long
const int N=2000;
const ll mod=1e9+7;
ll C[N+10][N+10];
void init()
{C[0][0]=1;for(int i=1;i<=N;i++){C[i][0]=1;for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;}
}
int n,m,a[N];ll ans;
int main()
{init();scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) scanf("%d",a+i);for(int i=0;i<n;i++){ll mu=1;for(int j=1;j<=m;j++)(mu*=C[a[j]+n-i-1][n-i-1])%=mod;(ans+=(i&1?-1ll:1ll)*C[n][i]*mu%mod)%=mod;}printf("%lld\n",(ans%mod+mod)%mod);return 0;
}

---

2018.10.18