P6078 [CEOI2004] Sweets题解

考虑将所有生成函数卷起来，得到
$$
\begin{aligned}
f(x)&=\frac{\prod_{i=1}^n1-x^{m_i+1}}{(1-x)^n}\\
&=\prod_{i=1}^{n}(1-x^{m_i+1})\cdot\sum_{j\ge0}\binom{n+j-1}{j}x^j\\
\end{aligned}
$$
$n\le10$ ，即可以暴力$dfs$
设当前算到的是 $x^k$ ,那么右边会对答案造成影响的项为 $\sum_{i=a-k}^{b-k}\binom{n+i-1}{i}x^i$
由组合数递推公式 $C_{i}^{j}=C_{i-1}^{j-1}+C_{i-1}^{j}$
可得:
$ C_{n+a}^a\quad=\quad 1\quad+\quad\sum_{i=1}^{a}C_{n+i-1}^{i} $
即设 $x^k$ 系数为 $s$ ,贡献为 $w$
$$
\begin{aligned}
w&=s\cdot\sum_{i=a-k}^{b-k}\binom{n+i-1}{i}\\
&=s\cdot\left(\sum_{i=1}^{b-k}C_{n+i-1}^i-\sum_{i=1}^{a-k-1}C_{n+i-1}^i \right)\\
&=s\cdot\left((C_{n+b-k}^{b-k}-1)-(C_{n+a-k-1}^{a-k-1}-1)\right)\\
&=s\cdot\left(C_{n+b-k}^{b-k}-C_{n+a-k-1}^{a-k-1}\right)\\
&=s\cdot\left(\frac{\prod_{i=1}^{n}(i+b-k)}{n!}-\frac{\prod_{i=1}^{n}(i+a-k-1)}{n!}\right)
\end{aligned}
$$