题意:(n)个箱子，第(i)个箱子有(a_i)朵花，在同一个的箱子里的所有花是同种颜色的.另外，不存在两个箱子中的花是相同颜色的.从这些箱子里选择(m)朵花,总共有多少种方式？因为结果有可能会很大，需要对(1e9+7)取模.至少有一个箱子中选择的花的数量不同才是两种不同的方案.
分析:本题即要求多重集的组合数.
多重集的组合数(无证明):
设(S={a_1*b_1,a_2*b_2,...,a_n*b_n})是由(a_1)个(b_1),(a_2)个(b_2,...,a_n)个(b_n)组成的多重集.设(sum=sum_{i=1}^na_i),对于任意整数(m<=sum),从(S)中取出(m)个元素组成一个多重集(不考虑顺序),产生的不同多重集的数量为:
(C_{n+m-1}^{n-1}-sum_{i=1}^nC_{n+m-a_i-2}^{n-1}+sum_{n+m-a_1-a_j-3}^{n-1}-...+(-1)^nC^{n-1}_{n+m-sum a_i-(n+1)})
本题的答案就是上式.但因为本题中的(m,a_i)都非常大,直接求肯定会超时,而(n)只有20,所以可以考虑二进制优化.
枚举(x=0)~(2^n-1),如果(x)在二进制表示下共有(p)位为1,假设分别是第(i_1,i_2,...,i_p)位,则这个(x)就代表上式中的一项((-1)pC^{n-1}_{n+m-a_{i_1}-a_{i_2}-...-a_{i_p}-(p+1)}).特别地,x=0,代表(C_{n+m-1}^{n-1}).
计算组合数时的优化,以求(C_{n+m-1}^{n-1})为例,(C_{n+m-1}^{n-1}=(n+m-1)!/(n-1)!m!=(m+1)(m+2)...(n+m-1)/(n-1)!),分母只剩下((n-1)!),可以直接用逆元了.
#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline LL read(){
LL s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
const int mod=1e9+7;
LL n,m,ans,a[25],inv[25];
inline int ksm(int a,int b){//快速幂板子
int c=1;
while(b){
if(b&1)c=(1ll*c*a)%mod;
a=(1ll*a*a)%mod;
b>>=1;
}
return c%mod;
}
inline int C(LL y,int x){//组合数板子
if(x<0||y<0||y<x)return 0;
y%=mod;int cnt=1;
for(int i=0;i<x;i++)
cnt=(1ll*cnt*(y-i))%mod;
for(int i=1;i<=x;i++)
cnt=(1ll*cnt*inv[i])%mod;
return cnt;
}
int main(){
for(int i=1;i<=20;i++)inv[i]=ksm(i,mod-2)%mod;
//预先处理出逆元
n=read();m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int x=0;x<(1<<n);x++){//二进制优化
if(x==0)ans+=C(n+m-1,n-1);
else{
int p=0;LL t=n+m;
for(int i=0;i<=n;i++){
if((x>>i)&1){//x的这一位是1
++p;//统计个数
t-=a[i+1];
//注意这里不是减a[i],因为二进制是从0位开始算起的
}
}
t=t-p-1;
if(p&1)ans=(ans-C(t,n-1))%mod;
else ans=(ans+C(t,n-1))%mod;
}
}
printf("%lld
",(ans+mod)%mod);
return 0;
}