多项式复合方程与远处求值

· · 算法·理论

为啥我在学这个？

:::info[yukicoder No.3399. One Two Three Two Three]{open} 有一个初值为 1 的变量 x，你可以执行下面两类操作任意多次：

给定整数 N，你需要计算有多少种操作方案能使得最终的 x=N。

::: 显然可以列出关于答案 OGF $F(z)$ 的复合方程： $$ \begin{aligned} F(z)&=z+(z+z^2+z^3)F(z)+F(z^2)+F(z^3)\\ F(z)&=\frac{z+F(z^2)+F(z^3)}{1-z-z^2-z^3}\\ \end{aligned} $$ 所求即为 $[z^N]F(z)$，这是一个远处求值问题，考虑使用 Bostan-Mori 算法。我们将其拆成三部分分别统计，$[z^N]\dfrac{z}{1-z-z^2-z^3}$ 就是朴素的远处求值。 对于 $[z^N]\dfrac{F(z^2)}{Q(z)}$，上下同乘 $\overline{Q}(z)=Q(-z)$，可知分母仅含 $z^{2i}$ 项（不妨记作 $Q'(z^2)$），于是只要将 $F(z^2)\overline{Q}(z)$ 拆成 $F(z^2)(\overline{Q}_0(z^2)+z\overline{Q}_1(z^2))$，并根据 $N$ 的奇偶性决定递归计算 $[z^{\lfloor\frac{N}{2}\rfloor}]\dfrac{F(z)\overline{Q}_0(z)}{Q'(z)}$ 还是 $[z^{\lfloor\frac{N}{2}\rfloor}]\dfrac{F(z)\overline{Q}_1(z)}{Q'(z)}$ 即可。 对于 $[z^N]\dfrac{F(z^3)}{Q(z)}$，我们有类似的处理方法，取 $\overline{Q}(z)=Q(\omega z)Q(\omega^2 z)$ 即可。 :::info[为啥 $Q(z)Q(\omega z)Q(\omega^2 z)$ 仅含三次项]{open} 考察 $Q(z)$ 的所有根，记作 $\displaystyle Q(z)=a\prod_{i=1}^m(b_i-z)$，则 $(b-z)(b-\omega z)(b-\omega^2 z)=z^3(\frac{b}{z}-1)(\frac{b}{z}-\omega)(\frac{b}{z}-\omega^2)=z^3((\frac{b}{z})^3-1)=b^3-z^3$，所以 $\displaystyle Q(z)Q(\omega z)Q(\omega^2 z)=a^3\prod_{i=1}^m(b_i^3-z^3)$。 这同时指出我们可以简单地通过三次方多项式的所有根（以及首项系数）来得到 $Q'(z)$，这一理解对后文优化有用。 ::: 那么递归下去就能得到一个看上去有点道理的做法，可惜要算的项数有点爆，下面我们处理一下。 缩减项数的一个直观想法是发现递归过程中 $N$ 必然形如 $\lfloor\dfrac{N}{2^i3^j}\rfloor$，这只有 $\Theta(\log^2 N)$ 个，所以如果能把所有 $(i,j)$ 相同的 $\dfrac{P(z)}{Q(z)}$ 加起来再一起递归下去，就能保证项数是对的。但是 $P,Q$ 的次数看上去又容易爆了，怎么办？ 通分时影响次数的关键因素是分母之间的关系，所以接下来我们重点关注一下分母 $Q$ 的变化。设 $\mathcal{F}_2(Q)$ 为满足 $Q'(z^2)=Q(z)Q(-z)$ 的多项式 $Q'$，$\mathcal{F}_3(Q)$ 同理。则根据上文的分析，我们知道： - $\mathcal{F}_i(F\times G)=\mathcal{F}_i(F)\times\mathcal{F}_i(G)$； - $\mathcal{F}_2(\mathcal{F}_3(Q))=\mathcal{F}_3(\mathcal{F}_2(Q))$。 设 $B=1-z-z^2-z^3$。初始时 $Q=1$，而迭代一次后 $Q$ 会变成 $\mathcal{F}_2(QB)$ 或 $\mathcal{F}_3(QB)$，所以我们总是可以不断应用上述两条性质把 $Q$ 表示成 $\displaystyle \prod_{i,j}\mathcal{F}_2^{\lang i\rang}(\mathcal{F}_3^{\lang j\rang}(B))$ 的形式，更具体的，如果当前状态为 $(i,j)$，则所有可能得到的 $Q$ 通分后一定形如 $\displaystyle \prod_{i'\le i\land j'\le j}\mathcal{F}_2^{\lang i'\rang}(\mathcal{F}_3^{\lang j'\rang}(B))$，这个式子的次数仅为 $\Theta(\log^2 N)$，所以 $P$ 的次数也被限制在 $\Theta(\log^2 N)$ 内。 每次迭代时需要计算若干个规模为 $\Theta(\log^2 N)$ 的多项式乘法，一共要计算 $\Theta(\log^2 N)$ 项，故总时间复杂度为 $\Theta(\log^4 N\log\log N)$。 实现上，可以注意 $Q(\omega z)Q(\omega^2 z)$ 的计算并不需要扩域，这是因为将 $Q$ 根据次数 ${\!}\bmod 3$ 分类为 $Q_0+Q_1+Q_2$ 后 $Q(\omega z)Q(\omega^2 z)$ 就等于 $Q_0^2+Q_1^2+Q_2^2-Q_0Q_1-Q_0Q_2-Q_1Q_2$，并且可以改写为 $(Q_0-Q_1)(Q_0-Q_2)+(Q_1-Q_2)^2$ 来做到只需两次卷积。 <https://yukicoder.me/submissions/1175623>。 习题：CF1864H Asterism Stream、P11284 「GFOI Round 2」Strings。