正解:容斥+$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=+,mod=;

int tot,poww[N]={},n,s,f[N],as;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il int power(ri x,ri y){ri ret=;while(y){if(y&)ret=1ll*ret*x%mod;x=1ll*x*x%mod;y>>=;}return ret;}

il int C(ri x,ri y)

{

    if(x<y)return ;y=min(y,x-y);ri multi=,inv=;

    rp(i,,y)multi=1ll*multi*(x-i+)%mod,inv=1ll*inv*i%mod;

    return 1ll*multi%mod*power(inv,mod-)%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=,cnt=s;

    rp(i,,n-)if(zt&(poww[i]))del=-del,cnt-=f[i+]+;

    if(cnt<)return;

    as=(as+1ll*lucas(cnt+n-,n-)*del%mod+mod)%mod;

}

signed main()

{

//    freopen("451e.in","r",stdin);freopen("451e.out","w",stdout);

    n=read();s=read();rp(i,,n)f[i]=read(),poww[i]=poww[i-]<<;

    rp(i,,poww[n]-)cal(i);printf("%lld\n",as);

    return ;

}

放下代码趴$QAQ$

巴特西

CF451E Devu and Flowers 数论

正解:容斥+$Lucas$定理+组合数学

解题报告:

最新文章

热门文章