泰勒展开 + 多项式 $\exp$ 处理多重背包计数.
这题的数据有锅,原本的题面是 $a_i>0$ 的,但 std 数据造错了,造出了 $a_i=0$ 的数据,甚至有 $a_i=b_i=0$ 导致答案为 $\infty$ 的数据,但管理员修的时候以为是题面数据范围写错了,就把题面改掉了.
$a_i=0$ 可以直接忽略它,最后将方案数乘上 $b_i+1$ ,于是在接下来的分析以及代码中都不考虑 $a_i=0$ 的情况.
无限背包可以转化成多重背包,将 $b_i$ 调整为最多能放下的物品数目即可,于是只用考虑多重背包的计数.
考虑写出答案的生成函数 $A(x)$ ,
$$
A(x)=\prod_{i=1}^m (\sum_{k=0}^{b_i} x^{k\cdot a_i})=\prod_{i=1}^m \frac{1-x^{(b_i+1)\cdot a_i}}{1-x^{a_i}}
$$
直接求乘积需要先做 $m$ 次多项式求逆,时间复杂度不能接受.
考虑将两边同时取对数,得到
$$
\ln A(x)=\sum_{i=1}^{m} \ln(1-x^{(b_i+1)\cdot a_i})-\ln(1-x^{a_i})
$$
设 $f(k)=\ln(1-x^k)$ ,将它在 $x_0=0$ 处做泰勒展开,得到
$$
f(k)=\ln(1-x^k)=-\sum_{i=1}^{\infty} \frac{x^{ki}}{i}
$$
把相同的 $\ln (1-x^k)$ 合并同类项后,对每个 $k$ ,暴力枚举 $i$ ,将次数 $\le n$ 的贡献加入 $\ln A(x)$ 中.
每个 $k$ 需要枚举的次数是 $\frac{n}{k}$ ,而最多只有 $2m$ 个不相同的 $k$ 需要枚举.
将 $m,n$ 看做同阶,根据调和级数的求和,在这一步就可以用 $O(n\log n)$ 的时间复杂度求出 $\ln A(x)$ .
最后再做一次多项式 $\exp$ 得到 $A(x)$ .
时间复杂度 $O(n\log n)$ .
1 | //%std |