Note

基础篇戳这里。

大概是记录 @Tiw 的伟大智慧叭。

嗷，附赠一个全家桶题。

Newton 迭代法
多项式乱算
常系数齐次线性递推

Newton 迭代法

解多项式方程

[f(u,x)equiv0pmod{x^n} ]

其中 (u) 是一个多项式。

用倍增的思想。设

[u_nequiv0pmod{x^n} ]

现要求 (u_{2n})。显然 (u_{2n}) 亦有 (u_{2n}equiv0pmod{x^n})，所以对于 (kin[2,+infty)capmathbb N)，有 ((u_{2n}-u_n)^kequiv0pmod{x^2n})。考虑在(mod x^{2n}) 意义下把 (f(u_{2n},x)) Tayler 展开，有

[f(u_{2n},x)=sum_{i=0}^{+infty}frac{f_{u}^{(i)}(u_n)}{i!}(u_{2n}-u_n)^iequiv0pmod{x^{2n}} ]

根据上文结论，得到：

[f(u_{2n},x)=f(u_n,x)+f_u'(u_n,x)cdot(u_{2n}-u_n)equiv0pmod{x^{2n}} ]

最终有

[u_{2n}=u_n-frac{f(u_n,x)}{f_u(u_n,x)}pmod{x^{2n}} ]

附赠例题（密码 ltytxdy）。

多项式乱算

该来的还是来了！

多项式求逆

给定多项式 (v)，求满足 (uvequiv1pmod{x^n}) 的 (u)。

迭代思想。

[egin{cases}u_nvequiv1pmod{x^n}\u_{2n}vequiv1pmod{x^{2n}}end{cases}\Rightarrow~~~~(u_{2n}-u_n)^2equiv0pmod{x^{2n}}\Rightarrow~~~~u_{2n}^2-2u_{2n}u_n+u_n^2equiv0pmod{x^{2n}}\Rightarrow~~~~u_{2n}-2u_n+u_n^2vequiv0pmod{x^{2n}}\Rightarrow~~~~u_{2n}equiv u_n(2-u_nv)pmod{x^{2n}} ]

(mathcal O(nlog n)) 计算即可。

多项式 (ln)

给定多项式 (v)，保证 (v_0=1)，求 (uequivln vpmod{x^n})。

直接（？）法：

[egin{aligned}u&=int v'ln'v~ ext dx\&=intfrac{v'}{v} ext dxend{aligned} ]

对多项式求导和积分都是 (mathcal O(n)) 的，所以求个逆就 (mathcal O(nlog n)) 算出来啦。

多项式 (exp)

给定多项式 (v)，保证 (v_0=0)，求 (uequivexp vpmod{x^n})。

方便求导的家伙直接丢到牛迭里去。（

解方程 (f(u,x)=ln(u)-vequiv0pmod{x^n})，牛迭式：

[u_{2n}equiv u_n-frac{ln(u_n)-v}{frac{1}{u_n}}=u_n(1-ln(u_n)+v)pmod{x^{2n}} ]

单次求 (ln) 和卷积，还是 (mathcal O(nlog n))。

多项式开根

给定多项式 (v)，求 (uequiv v^{frac{1}2}pmod{x^n})。

牛迭，解 (f(u,x)=u^2-vequiv0pmod{x^n})，有：

[u_{2n}=u_n-frac{u_n^2-v}{2u_n}=frac{u_n^2+v}{2u_n}pmod{x^{2n}} ]

单次卷积和求逆，复杂度 (mathcal O(nlog n))。

多项式带余除法

给定多项式 (u,v)，求 (uequiv vp+rpmod{x^n})，且 (deg r<deg v)。（(deg u) 表示 (u) 的最高次。）

考虑一个灵性的变换，对于任意多项式 (u)，令其“翻转”多项式为 (u_r)，有：

[u_r=x^{deg u}u(x^{-1}) ]

显然翻转操作对于加法和卷积都是可分配的。

把翻转作用于原式两边，得到：

[u_requiv v_rp_r+x^{deg u-deg v+1}r_rpmod{x^n} ]

又由于 (deg p_r=deg u-deg v)，所以把模数换成 (x^{deg u-deg v+1})，后一项直接模掉，求出来的还是 (p_r)，即：

[p_requivfrac{u^r}{v^r}pmod{x^{deg u-deg v+1}} ]

求出 (p_r)，瞎算算就求到 (p) 和 (r) 了，复杂度还是 (mathcal O(nlog n))。

多项式快速幂

给定多项式 (v) 和整数 (k)，求 (u=v^kpmod{x^n})。

假设我们能够对 (v) 求 (ln)，则左右同时 (ln) 再 (exp) 得到：

[u=exp(kln v) ]

(mathcal O(nlog n)) 搞定。

可惜有时候求不得，需要把 (v_0) 调整成 (1)。位移+系数提公因数即可。

多项式三角函数

给定多项式 (v)，求 (u=sin v)（或 (cos v) 等）。

Euler 公式：

[e^{ix}=cos x+isin x ]

考虑对称性，也有：

[e^{-ix}=cos x-isin x ]

把多项式 (v) 代入，求出 (e^{iv}) 和 (e^{-iv})，就能直接解出 (sin v) 和 (cos v)。

虚数单位 (i) 即 (omega_4^1)，用原根替代单位根即可。复杂度 (mathcal O(nlog n))。

常系数齐次线性递推

Link.

求一个满足 (m) 阶齐次线性递推数列 ({a}) 的第 (n) 项，即求

[a_n=sum_{i=1}^mf_ia_{n-i} ]

不用多项式取模的做法。

根据条件式子得到：

[A(x)=F(x)A(x)+P(x) ]

(P(x)) 某个多项式，用于修补低次项。

变形：

[egin{aligned}A(x)&=F(x)A(x)+P(x)\Rightarrow~~~~A(x)&=frac{P(x)}{Q(x)}~~~~ ext{let } Q(x)=1-F(x)\Rightarrow~~~~A(x)&=frac{P(x)Q(-x)}{Q(x)Q(-x)}end{aligned} ]

对于任意奇数 (k)，考虑 (Q(x)Q(-x)) 的 (k) 次项：

[[x^k]Q(x)Q(-x)=sum_{i=0}^k(-1)^iq_iq_{k-i} ]

由于 (2 ot|k)，故 ((-1)^iq_iq_{k-i}+(-1)^{k-i}q_{k-i}q_i=0)，原式为 (0)，即 (Q(x)Q(-x)) 仅含偶次项。不妨令 (R(x^2)=Q(x)Q(-x))，代入变形：

[egin{aligned}A(x)&=frac{P(x)Q(-x)}{R(x^2)}\Rightarrow A(x)&=frac{E(x^2)}{R(x^2)}+xfrac{O(x^2)}{R(x^2)}~~~~ ext{let }egin{cases}E(x)=sum_i [x^{2i}]P(x)Q(-x)cdot x^i\O(x)=sum_i [x^{2i+1}]P(x)Q(-x)cdot x^iend{cases}end{aligned} ]

我们要求的只是 ([x^n]A(x)) 而非整个 (A(x))，所以只需要根据 (n) 的奇偶性递归到其中一边求解。复杂度仍然是 (mathcal O(mlog mlog n))，不过常数会小很多。

此算法基础上的更多卡常技巧请见 EI 的博客。