正解:容斥+Lucas定理+组合数学
解题报告:
先mk个我不会的母函数的做法,,,
首先这个题的母函数是不难想到的,,,就$\left ( 1+x_{1}^{1}+x_{1}^{2}+...+x_{1}^{f_{1}}\right )\cdot\left ( 1+x_{2}^{1}+x_{2}^{2}+...+x_{2}^{f_{2}}\right )\cdot...\cdot\left ( 1+x_{n}^{1}+x_{n}^{2}+...+x_{n}^{f_{n}}\right )$
显然ans就$x^{s}$的系数
但是因为$f[i]$和$s$挺大的,,,所以这个方法就$GG$了,,,似乎$luogu$有个题解写的这个但我也麻油系统地学过母函数就先咕辽,$just$先$mk$下思路QAQ
下面港下我会滴解法趴$QAQ$
考虑这种求合法方案的,自然而然就应该想到总数-不合法方案嘛
首先总数就相当于不考虑$f[i]$的限制,于是$ans=\binom{s+n-1}{s}$,不解释,就可重集合组合数公式罢辽
然后对于不合法的,显然就枚举有几个$f[i]$被爆了,容斥一下就好,感觉好像之前做过一道类似的题目鸭,太套路了不解释,,,
然后记得套个Lucas,因为实在太基操了就只顺口一提辽没什么可细港的QAQ
(upd:,,,我发现真的做过,,,$dbq$我忘了,,,王之财宝,只是数据范围小一下,,,$maya$我真的服了自己了,,,做过的题居然能忘,,,我枯了$gql$真是太辣鸡了,,,
#include<bits/stdc++.h> using namespace std; #define il inline #define gc getchar() #define t(i) edge[i].to #define int long long #define ri register int #define rb register bool #define rc register char #define rp(i,x,y) for(ri i=x;i<=y;++i) #define my(i,x,y) for(ri i=x;i>=y;--i) #define e(i,x) for(ri i=head[x];i;i=edge[i].nxt) const int N=20+10,mod=1000000007; int tot,poww[N]={1},n,s,f[N],as; il int read() { rc ch=gc;ri x=0;rb y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=gc; if(ch=='-')ch=gc,y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } il int power(ri x,ri y){ri ret=1;while(y){if(y&1)ret=1ll*ret*x%mod;x=1ll*x*x%mod;y>>=1;}return ret;} il int C(ri x,ri y) { if(x<y)return 0;y=min(y,x-y);ri multi=1,inv=1; rp(i,1,y)multi=1ll*multi*(x-i+1)%mod,inv=1ll*inv*i%mod; return 1ll*multi%mod*power(inv,mod-2)%mod; } int lucas(ri x,ri y){if(x<=mod)return C(x,y);return 1ll*C(x%mod,y%mod)*lucas(x/mod,y/mod)%mod;} il void cal(ri zt) { ri del=1,cnt=s; rp(i,0,n-1)if(zt&(poww[i]))del=-del,cnt-=f[i+1]+1; if(cnt<0)return; as=(as+1ll*lucas(cnt+n-1,n-1)*del%mod+mod)%mod; } signed main() { // freopen("451e.in","r",stdin);freopen("451e.out","w",stdout); n=read();s=read();rp(i,1,n)f[i]=read(),poww[i]=poww[i-1]<<1; rp(i,0,poww[n]-1)cal(i);printf("%lld\n",as); return 0; }