题目描述
传送门
题目大意：有n个盒子，每个盒子中有fi个物品，从每个盒子中选取不超过fi的物品，使物品总数为s的方案数。
题解
利用容斥原理： ans=至少0个超过限制的-至少一个超过限制的+至少两个超出限制的-……
那么如果不考虑限制，那么相当于把s个物品放到n个盒子中允许为空的方案数。
我们可以先固定哪些盒子超过了限制，s-=(fi+1),然后在随便放。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
#define p 1000000007
using namespace std;
LL f[1<<21],a[21],s,inv,n;
LL calc(LL n1,LL m1)
{
LL ans=1;
for (LL i=n1-m1+1;i<=n1;i++) {
LL t=i%p;
ans=(LL)ans*t%p;
}
ans=ans*inv%p;
return ans;
}
LL quickpow(LL num,int x)
{
LL ans=1; LL base=num%p;
while (x) {
if (x&1) ans=base*ans%p;
x>>=1;
base=base*base%p;
}
return ans;
}
int main()
{
freopen("a.in","r",stdin);
scanf("%I64d%I64d",&n,&s);
for (LL i=0;i<n;i++) scanf("%I64d",&a[i]);
inv=1;
for (LL i=1;i<=n-1;i++) inv=inv*i%p;
inv=quickpow(inv,p-2);
LL ans=0;
for (int i=0;i<(1<<n);i++) {
int cnt=0; LL sum=s;
for (int j=0;j<n;j++)
if (i&(1<<j)) {
++cnt;
sum-=(a[j]+1);
}
if (sum>=0) sum=calc(sum+n-1,n-1);
else sum=0;
if (cnt&1) ans=(ans-sum+p)%p;
else ans=(ans+sum)%p;
}
printf("%I64d\n",ans);
}