P3784 [SDOI2017] 遗忘的集合 题解

· · 题解

题意

给定只用 S 中元素的分拆方案数，求 S。

分析

考虑设题目中的分拆方案的 OGF 为 F(x)，众所周知，不设限制的分拆方案是 \prod_{i=1}^\infty \frac{1}{1-x^i}，本题中的唯一限制“元素一定出现在集合 S 中”也很好处理，直接套在指数上即可，为了方便起见我们设 g(i) 为 [i \in S]，这样就能表示出 F(x) 了：

F(x) = \prod_{i=1}^\infty (\frac{1}{1-x^i})^{g(i)}

之后是对这个式子进行化简， \prod 不好处理，直接取 \ln：

\ln(F(x)) = -\sum_{i=1}^\infty g(i)\ln(1-x^i)

后面是一个经典的形式，我们知道它等于 -\sum_{j=1}^\infty \frac{x^{ij}}{j}，果断展开：

\ln(F(x)) = \sum_{i=1}^\infty g(i)\sum_{j=1}^\infty \frac{x^{ij}}{j}

变量上两个指标比较烦，换元试试：

\ln(F(x)) = \sum_{i=1}^\infty x^i \sum_{d \mid i}\frac{g(d)d}{i}

提取系数：

[x^n]\ln(F(x)) = \sum_{d \mid n} \frac{g(d)d}{n}

这不是莫反嘛，我们设 G(n) = g(n) * n,H(n) = n[x^n]\ln(F(x)) ，那么：

H=G*I \Leftrightarrow G = H * \mu

反演出来就做完了，注意到我们只要求那些位置有值，可以直接枚举有值的位置在它的倍数处减去这个值，调和级数的求即可。