多项式复合与复合逆之新科技
dengyaotriangle
·
·
算法·理论
简介
noshi91 提供了一个新 trick [1]，降低了很多经典问题的复杂度，并且该算法是 practical 的，好写又快。
原算法
考虑对于形式幂级数 f，如何求 [x^k] f^0,[x^k]f^1,\ldots [x^k] f^{n-1}.
考虑二元形式幂级数
[x^k]\frac{1}{1- y f}=[x^k]\sum_k y^k f^k=\sum_k y^k [x^k]f^k,
实际上只需要求出 [x^k]\frac{1}{1-yf} 即可。
使用 Bostan-Mori 算法。即对于
[x^k]\frac{f(x,y)}{g(x,y)},
每次将分子分母乘上 g(-x,y), 变成
[x^k]\frac{f(x,y)g(-x,y)}{g(x,y)g(-x,y)},
此时 g(x,y)g(-x,y) 没有 x 的奇数次项，可以写成 h(x^2,y), 至于分子可以分离其奇偶次项，得到 f(x,y)g(-x,y)=a(x^2,y)+xb(x^2,y).
那么就是求
[x^k] \frac{a(x^2,y)}{h(x^2,y)}+ x \frac{b(x^2,y)}{h(x^2,y)}.
若 k 是奇数，则只有前一项有用，若 k 是偶数，则只有前一项有用。此时只保留这一项，那么就相当于求
[x^{k/2}]\frac{a(x,y)}{h(x,y)}, [x^{(k-1)/2}] \frac{b(x,y)}{h(x,y)}
中的某一个。
不断递归，直到 k=0， 此时即求 \frac{f(0,y)}{g(0,y)}.
考虑分析过程中多项式次数。每次 x 需要保留的次数减半（因为只需要求到 k/2 次项），而 y 的次数至多加倍。所以过程中 x,y 次数的乘积永远是 O(n) 的。
使用二元 FFT 等计算卷积，一轮复杂度 O(n\log n)，总复杂度 O(n\log^2n).
多项式复合——转置原理
多项式复合可以写成
f_j=\sum_{i=0}^{n-1} g_i [x^j]h^i.
利用转置原理，其转置问题即
g_i=\sum_{j=0}^{n-1} f_j [x^j]h^i.
若令 F(x)=\sum_{i=0}^{n-1} x^i f_{n-1-i}， 那么
g_i=\sum_{j=0}^{n-1} [x^{n-1-j}] F [x^j]h^i=[x^{n-1}] F h^i.
所以即求 BGF
[x^{n-1}]\frac{F}{1-y h}
利用前面介绍的做法，即 O(n\log^2n) 解决。
多项式复合逆——牛顿迭代
通过多项式复合，可以立刻通过牛顿迭代求复合逆。
具体来讲，若 F(G(x))=x，而 F(G_i(x))\equiv x \pmod {x^i}，那么
x=F(G(x))\equiv F(G_i(x))+ F'(G_i(x))(G(x)-G_i(x)) \pmod{x^{2i}}.
通过多项式复合，每次精度翻倍，复杂度
T(n)=T(n/2)+O(n\log^2n)=O(n\log^2n).
多项式复合逆——拉格朗日反演
也可以通过拉格朗日反演直接得到复合逆。根据 [2]，
[x^k] F^i=\frac{i}k [x^{k-i}] \left(\frac{G}{x}\right)^{-k}.
左侧直接利用之前介绍的方法求得，那么即求出了 \left(\frac{G}{x}\right)^{-k}，就可以解出来 G 了。
实现
咕
应用
已经不管我的事了，我已经退役了
列欧拉数直接就是多项式复合。现在可以 practical 地求了。
后面的忘了。
参考文献
- 原作者： https://noshi91.hatenablog.com/entry/2024/03/16/224034
- https://codeforces.com/blog/entry/77551