题目描述
Devu想用花去装饰他的花园，他已经购买了n个箱子，第i个箱子有fi朵花，在同一个的箱子里的所有花是同种颜色的（所以它们没有任何其他特征）。另外，不存在两个箱子中的花是相同颜色的。 现在Devu想从这些箱子里选择s朵花去装饰他的花园，Devu想要知道，总共有多少种方式从这些箱子里取出这么多的花？因为结果有可能会很大，结果需要对1000000007取模。 Devu认为至少有一个箱子中选择的花的数量不同才是两种不同的方案。 输入输出格式 输入格式：
第一行包含两个用空格分开的整数n和s 第二行包含n个用空格分开的整数fi 输出格式：
输出一个整数，Devu的方案数对1000000007取模 说明
样例1：选3朵花两种方案：1,2 和 0,3 样例2：选4朵花只有一种方案：2,2 样例3：选5朵花三种方案：1,2,2 和 0,3,2 和 1,3,1
输入输出样例
输入样例#1：
2 3
1 3
输出样例#1：
2
输入样例#2：
2 4
2 2
输出样例#2：
1
输入样例#3：
3 5
1 3 2
输出样例#3：
3
题解:
用多重集的组合数求解本题
注意把C(n+m-1,x)=P(x,n-1)/(n-1)即可降为O(2^n)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int a[23],inv[23],n,s,ans;
int ksm(int a,int b) {
int ans=1;
while(b) {
if(b&1) ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
int C(int n,int m) {
if(n<0 || m<0 || n<m) return 0;
n%=mod;
if(!n || !m) return 1;
int ans=1;
for(int i=0;i<=m-1;i++) ans=(ans*(n-i))%mod;
for(int i=1;i<=m;i++) ans=(ans*inv[i])%mod;
return ans;
}
signed main() {
for(int i=1;i<=20;i++) inv[i]=ksm(i,mod-2);
cin>>n>>s;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=0;i<=(1<<n)-1;i++) {
if(i==0) ans=(ans+C(n+s-1,n-1))%mod;
else {
int now=n+s,cnt=0;
for(int j=0;j<n;j++) if((i>>j)&1) {
cnt++;
now-=a[j+1];
}
now-=(cnt+1);
if(cnt&1) ans=(ans-C(now,n-1))%mod;
else ans=(ans+C(now,n-1))%mod;
}
}
cout<<(ans+mod)%mod;
return 0;
}