Description
前置芝士:二项式反演
题意:给定 \(m\) 种物品,每种物品有 \(m_i\) 个且同种物品均相同,求放进 \(n\) 个不同盒子,每个盒子非空的方案数。
Solution
假设每个盒子先铺一个物品,因为每种物品个数有限制,所以把方案建立在盒子非空的基础上想不太好做。
但如果要求盒子可为空,那么每种物品的方案就是有限可重集方案数。
又因为每个盒子的物品没有顺序,所以把物品依种类放入即可。
接着上面盒子可为空的思路想,令 \(f(k)\) 表示把所有物品放入 \(k\) 个盒子,这 \(k\) 个可为空且另 \(n-k\) 个盒子一定为空的方案数。有
若 \(k\) 个盒子钦定,那么 \(f(k)\times\binom{n}{k}\) 表示至少有 \(n-k\) 个盒子为空的方案数。
再设 \(g(k)\) 表示恰好有 \(n-k\) 个盒子为空的方案数。易得
由二项式反演有
\[g(k)=\sum_{i=k}^n(-1)^{k-i}\binom{i}{k}f(i) \]再看题目,要求的不正是 \(g(0)\) 么?
于是这道题就愉快地结束了~
Code:
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=2005;
const int N=2000;
const int Mod=1e9+7;
#define ll long long
int n,m;
ll fra[MAXN],ofra[MAXN],a[MAXN],o[2],Ans;
ll ksm(ll a,int b){
ll ans=1;
while(b){
if(b&1) ans=ans*a%Mod;
a=a*a%Mod;b>>=1;
}
return ans;
}
ll C(int n,int m){
if(n<m) return 0;
return ofra[m]*(fra[n]*ofra[n-m]%Mod)%Mod;
}
int main(){
fra[0]=1;o[1]=-1;o[0]=1;
for(int i=1;i<=N;i++){
fra[i]=fra[i-1]*i%Mod;
}
ofra[N]=ksm(fra[N],Mod-2);
for(int i=N;i;i--){
ofra[i-1]=ofra[i]*i%Mod;
}
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%lld",&a[i]);
}
for(int i=0;i<=n;i++){
ll tmp=1;
for(int j=1;j<=m;j++){
tmp=(tmp*C(n-i+a[j]-1,n-i-1))%Mod;
}
tmp=tmp*C(n,i)%Mod;
Ans=(Ans+o[i%2]*tmp)%Mod;
}
printf("%lld\n",(Ans+Mod)%Mod);
return 0;
}
\(\Bbb{End.}\)
\(\Bbb{Thanks}\) \(\Bbb{For}\) \(\Bbb{Reading.}\)