菜王的 blog

子集卷积 / 求逆

这个不用多说了。把一维变为两维，分别做 OR 卷积和普通的卷积。$\mathcal{O}(2^nn^2)$。

求逆就是乘法的逆运算。做正常的 $\mathcal{O}(n^2)$ 多项式暴力求逆即可。

exp / ln

我们使用类似子集卷积的技巧，集合幂级数 exp 就变成了要求出下面的这么一个 $g$：

$f_{k, S} = \sum_{|T_1| + |T_2| + \dots + |T_k| = |S|, T_1 \cup T_2 \cup \dots \cup T_k = S} \prod_{i = 1}^k a_{T_i}\\ g_S = \sum_{k = 0}^{|S|} \frac{f_{k, S}}{k!}\\$

并起来恰好等于的限制不好处理，我们做个高维前缀和，使得每个 $T_k$ 之间相互独立，这样就可以转化成多项式 exp 了；最后再差分回去。

${f'}_{k, S} = \sum_{T_i \subseteq S, |T_1| + |T_2| + \dots + |T_k| = |S|} \prod_{i = 1}^k a_{T_i}\\ {F'}_S(x) = \sum_{T \subseteq S} a_Tx^{|T|}\\ {G'}_S(x) = \sum_{k = 0}^{|S|} \frac{{F'}_S^k}{k!} = \exp({F'}_S)\\$

求出所有的 ${F'}_S$ 可以 $\mathcal{O}(2^nn^2)$ 完成，那么对于每一个 $S$ 都暴力 $\mathcal{O}(n^2)$ exp 即可求出 $G'$。最后差分回去即可得到 $G$，有 $g_s = [x^{|S|}]G_S(x)$。

ln 是 exp 的逆运算，考虑反过来依次撤销 exp 的三个操作，就是做高维前缀和，做多项式 ln，再差分回去。

总结下来就是，集合幂级数 卷积 / 求逆 / exp / ln 的流程就是，先做高维前缀和，再分别做多项式 卷积 / 求逆 / exp / ln，再差分回去。

逐点牛顿迭代

考虑集合幂级数 exp 的组合意义，把 $[n]$ 无序的划分为若干个集合，每个集合的权值乘积之和。直接考虑一个 dp：$f_{i, j, S}$ 表示已经考虑了前 $i$ 个元素，划分了 $S$ 内的元素，还需要划分出 $j$ 个集合的方案数。转移是显然的：

$f_{i - 1, j, S} \to f_{i, j, S} \ (i \in S)\\ f_{i - 1, j, S} \times g_T \to f_{i, j - 1, S \cup T} \ (\max T = i, S \cap T = \varnothing) \\$

可以用子集卷积优化。

分析一下时间复杂度，对于一个 $i$ 我们要做 $n - i$ 次大小为 $2^i$ 的子集卷积，是 $\sum_{i = 0}^n (n - i)2^ii^2$。显然有 $\sum_{i = 0}^n (n - i)2^i < 2^{n + 1}$，于是时间复杂度还是 $\mathcal{O}(2^nn^2)$ 的。

发现这个东西非常的厉害。如果要求的东西是 $\sum_{i \ge 0} a_i F^i$，那么直接把 dp 初值 $f_{0, i, \varnothing}$ 设为 $a_i i!$ 即可。

那么 exp 就是 $a_i = \frac 1{i!}$，ln 就是 $a_i = \frac{(-1)^{i - 1}}i$，k-exp 就是 $a_i = [i \le k]\frac 1{i!}$，求幂次就是 $a_i = [i = k]$，至于求逆可以先求 $\frac 1{1 - F(x)}$ 再变回来，$a_i = 1$。而且这些东西都不需要使用逆元。但是注意求逆需要保证 $F(\varnothing) = 1$。

如果可以使用逆元，但是不保证 $F(\varnothing) = 1$ 可以求出 $\frac 1{F(\varnothing)}$ 乘一下。