首先把 \(c\) 看做一个集合，然后定义 \(C(x) = \sum\limits_{i \in c} x^i\)。
再设 \(f_m\) 为总权值和为 \(m\) 时的答案。
根据某些 DP 套路，可以得到 \[ f_m = 1 + \sum\limits_{i \in c}\sum\limits_{j = 0}^{m - i} f_j f_{m-i-j} \]
令 \(F(x)\) 为 \(f\) 的生成函数，则根据上式有 \[ \begin{align*} F(x) &= CF^2(x) + 1 \\ CF^2(x) - F(x) + 1 &= 0 \\ F(x) &= \frac{1 \pm \sqrt{1 - 4C}}{2C} \end{align*} \]
由于 \(0 \not\in c,f_0 = 1\) 所以 \(C(0) = 0,F(0) = 1\)。
据此可知应取负号，即 \[
F(x) = \frac{1 - \sqrt{1 - 4C}}{2C}
\]
然后就发现似乎就可做了，但是 \(C\) 的常数项为 \(0\)，有点麻烦。
考虑用类似分母有理化的方法对分子有理化试试。
易得 \[
F(x) = \frac2{1+\sqrt{1-4C}}
\]
然后就完全可做了。
贴个多项式开根和多项求逆就做完了。
代码：
1 |
|