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

解题报告:

传送门!

先mk个我不会的母函数的做法,,,

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

首先这个题的母函数是不难想到的,,,就$\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}$

不解释,就可重集合组合数公式罢辽(好像组合数公式中写的是$\binom{s+n-1}{n-1}$,,,?差不多就变形了下,我$jio$得这样儿好看些所以就改了下$QwQ$

然后对于不合法的,显然就枚举有几个$f[i]$被爆了,容斥一下就好,太套路了不解释,感觉好像之前做过一道类似的题目鸭,,,

(upd:,,,我发现真的做过,,,dbq我忘了,,,王之财宝,只是数据范围小一下,,,maya我真的服了自己了,,,做过的题居然能忘,,,我枯了gql真是太辣鸡了,,,

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄