Description
有n个箱子，要选s支花，每个箱子有f[i]支花。同一个箱子的花颜色相同，不同箱子的花颜色不同，问说可以有多少种组合
Input
第一行输入两个整数n和s表示箱子数量和要选的花的数量，第二行n个整数表示每个花坛中花的数量
Output
输出从这n个箱子中选取s支花的方法数
Sample Input
3 5
1 3 2
Sample Output
3
Solution
首先隔板法sum个球放进n个盒子中允许盒子为空的方案是C(sum+n-1,n-1)，但是由于这里有个限制，即f[i]，这样计数的话某些花会超出其个数，所以我们应该2^n枚举从哪些箱子取的花的数量超出了f[i]，比如确定i超出个数其它不确定的方案C(sum-f[i]-1+n-1,n-1)，即sum-=f[i]+1（因为允许箱子为空一开始要人为在超了的箱子中加入一个球）
然后就是容斥原理ans=超0个-超1个+超2个……
其中求组合数C(n,m)时因为n和m较大故需用到lucas定理
lucas定理：C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)，前半部分继续递归用lucas定理，后半部分用组合数直接求
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const ll mod=1000000007ll;
ll mod_pow(ll a,ll b,ll p)//快速幂,求a^b(mod p)
{
ll ans=1;
a%=p;
while(b)
{
if(b&1)ans=ans*a%p;
b>>=1;
a=a*a%p;
}
return ans;
}
ll C(ll n,ll m)//求组合数C(n,m)
{
if(n<m)
return 0;
if(m>n-m)
m=n-m;
ll a=1,b=1;
for(ll i=0;i<m;i++)
{
a=a*(n-i)%mod;
b=b*(i+1)%mod;
}
return a*mod_pow(b,mod-2,mod)%mod;//费马小定理a^p=a(mod p)
}
ll lucas(ll n,ll m)//lucas定理求C(n,m)
{
ll ret=1;
while(n&&m)
{
ll a=n%mod,b=m%mod;
if(a<b)
return 0;
ret=ret*C(a,b)%mod;
n/=mod;
m/=mod;
}
return ret;
}
ll n,s,f[22];
int main()
{
while(~scanf("%I64d%I64d",&n,&s))
{
for(ll i=0;i<n;i++)
scanf("%I64d",&f[i]);
ll ans=0;
for(ll i=0;i<(1<<n);i++)//2^n枚举所有状态
{
ll flag=1,sum=s;
for(ll j=0;j<n;j++)//枚举所有箱子判断其是否会超
if(i&(1<<j))//
{
sum-=f[j]+1;//这个箱子超了则需在其中人为放一个球后再用隔板法
flag*=-1;//flag判断容斥时是加还是减
}
if(sum<0)//从超了的箱子中取的花的数量已经超过所需
continue;
ans+=flag*lucas(sum+n-1,n-1);//容斥
ans%=mod;
}
ans=(ans+mod)%mod;
printf("%I64d\n",ans);
}
return 0;
}