多项式 $\ln$ + 莫比乌斯反演.
Loj 556 是给出每种物品的体积,问填充背包的方案数,而这个题是给出填充背包的方案数,问各个物品的体积.
仍然考虑生成函数,设方案数的生成函数为 $F(x)$ ,集合 $S$ 是否包含 $i$ 记为 $a_i$ ,则
$$
F(x)=\prod_{i=1}^n (\frac{1}{1-x_i})^{a_i} \\
\ln(F(x))=\sum_{i=1}^n a_i\cdot \ln(\frac{1}{1-x_i}) \\
\ln(F(x))=\sum_{i=1}^n a_i\cdot \sum_{j=1}^{\infty} \frac{x^{ij}}{j} \\
\ln(F(x))=\sum_{i=1}^{\infty} x_i\cdot \sum_{d|i} a_d\cdot \frac{d}{i}
$$
将 $\ln(F(x))$ 求出,注意卷积要使用 MTT .
记 $\ln(F(x))$ 对应的数列为 $f$ ,则
$$
n\cdot f_n=\sum_{d|n} d\cdot a_d
$$
莫比乌斯反演,
$$
i\cdot a_i=\sum_{d|i} \mu(\frac{i}{d})\cdot d\cdot f_d
$$
预处理 $\mu$ 后,将每个 $d\cdot f_d$ 的贡献加到 $i$ 中,根据调和级数,时间复杂度 $O(n\log n)$ .
最后可以直接输出每个不为 $0$ 的 $i\cdot a_i$ ,因为 $a_i$ 只会是 $0,1$ .
写了一发 myy 的 $4$ 次 DFT 的 MTT ,注意这个做法中,虚部也存了信息,所以 IDFT 的时候不能只对实部除以 $n$.
1 | //%std |