Note - 多项式乱写
??基础篇戳。
??大概是记录 @Tiw 的伟大智慧叭。
??嗷，附赠一个 。
目录- Newton 迭代法
- 多项式乱算
- 多项式求逆
- 多项式 \(\ln\)
- 多项式 \(\exp\)
- 多项式开根
- 多项式带余除法
- 多项式快速幂
- 多项式三角函数
- 常系数齐次线性递推
Newton 迭代法
??解多项式方程
\[f(u,x)\equiv0\pmod{x^n} \]??其中 \(u\) 是一个多项式。
??用倍增的思想。设
\[u_n\equiv0\pmod{x^n} \]??现要求 \(u_{2n}\)。显然 \(u_{2n}\) 亦有 \(u_{2n}\equiv0\pmod{x^n}\)，所以对于 \(k\in[2,+\infty)\cap\mathbb N\)，有 \((u_{2n}-u_n)^k\equiv0\pmod{x^{2n}}\)。考虑在\(\bmod 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)^i\equiv0\pmod{x^{2n}} \]??根据上文结论，得到：
\[f(u_{2n},x)=f(u_n,x)+f_u'(u_n,x)\cdot(u_{2n}-u_n)\equiv0\pmod{x^{2n}} \]??最终有
\[u_{2n}=u_n-\frac{f(u_n,x)}{f_u(u_n,x)}\pmod{x^{2n}} \]??附赠（密码 ltytxdy）。
多项式乱算
??该 来 的 还 是 来 了！
多项式求逆
??给定多项式 \(v\)，求满足 \(uv\equiv1\pmod{x^n}\) 的 \(u\)。
??迭代思想。
\[\begin{cases}u_nv\equiv1\pmod{x^n}\\u_{2n}v\equiv1\pmod{x^{2n}}\end{cases}\\\Rightarrow~~~~(u_{2n}-u_n)^2\equiv0\pmod{x^{2n}}\\\Rightarrow~~~~u_{2n}^2-2u_{2n}u_n+u_n^2\equiv0\pmod{x^{2n}}\\\Rightarrow~~~~u_{2n}-2u_n+u_n^2v\equiv0\pmod{x^{2n}}\\\Rightarrow~~~~u_{2n}\equiv u_n(2-u_nv)\pmod{x^{2n}} \]??\(\mathcal O(n\log n)\) 计算即可。
多项式 \(\ln\)
??给定多项式 \(v\)，保证 \(v_0=1\)，求 \(u\equiv\ln v\pmod{x^n}\)。
??直接（？）法：
\[\begin{aligned}u&=\int v'\ln'v~\text dx\\&=\int\frac{v'}{v}\text dx\end{aligned} \]??对多项式求导和积分都是 \(\mathcal O(n)\) 的，所以求个逆就 \(\mathcal O(n\log n)\) 算出来啦。
多项式 \(\exp\)
??给定多项式 \(v\)，保证 \(v_0=0\)，求 \(u\equiv\exp v\pmod{x^n}\)。
??方便求导的家伙直接丢到牛迭里去。（
??解方程 \(f(u,x)=\ln(u)-v\equiv0\pmod{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(n\log n)\)。
多项式开根
??给定多项式 \(v\)，求 \(u\equiv v^{\frac{1}2}\pmod{x^n}\)。
??牛迭，解 \(f(u,x)=u^2-v\equiv0\pmod{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(n\log n)\)。
多项式带余除法
??给定多项式 \(u,v\)，求 \(u\equiv vp+r\pmod{x^n}\)，且 \(\deg r<\deg v\)。（\(\deg u\) 表示 \(u\) 的最高次。）
??考虑一个灵性的变换，对于任意多项式 \(u\)，令其“翻转”多项式为 \(u_r\)，有：
\[u_r=x^{\deg u}u(x^{-1}) \]??显然翻转操作对于加法和卷积都是可分配的。
??把翻转作用于原式两边，得到：
\[u_r\equiv v_rp_r+x^{\deg u-\deg v+1}r_r\pmod{x^n} \]??又由于 \(\deg p_r=\deg u-\deg v\)，所以把模数换成 \(x^{\deg u-\deg v+1}\)，后一项直接模掉，求出来的还是 \(p_r\)，即：
\[p_r\equiv\frac{u^r}{v^r}\pmod{x^{\deg u-\deg v+1}} \]??求出 \(p_r\)，瞎算算就求到 \(p\) 和 \(r\) 了，复杂度还是 \(\mathcal O(n\log n)\)。
多项式快速幂
??给定多项式 \(v\) 和整数 \(k\)，求 \(u=v^k\pmod{x^n}\)。
??假设我们能够对 \(v\) 求 \(\ln\)，则左右同时 \(\ln\) 再 \(\exp\) 得到：
\[u=\exp(k\ln v) \]??\(\mathcal O(n\log n)\) 搞定。
??可惜有时候求不得，需要把 \(v_0\) 调整成 \(1\)。位移+系数提公因数即可。
多项式三角函数
??给定多项式 \(v\)，求 \(u=\sin v\)（或 \(\cos v\) 等）。
??Euler 公式：
\[e^{ix}=\cos x+i\sin x \]??考虑对称性，也有：
\[e^{-ix}=\cos x-i\sin x \]??把多项式 \(v\) 代入，求出 \(e^{iv}\) 和 \(e^{-iv}\)，就能直接解出 \(\sin v\) 和 \(\cos v\)。
??虚数单位 \(i\) 即 \(\omega_4^1\)，用原根替代单位根即可。复杂度 \(\mathcal O(n\log n)\)。
常系数齐次线性递推
??Link.
??求一个满足 \(m\) 阶齐次线性递推数列 \(\{a\}\) 的第 \(n\) 项，即求
\[a_n=\sum_{i=1}^mf_ia_{n-i} \]??不用多项式取模的做法。
??根据条件式子得到：
\[A(x)=F(x)A(x)+P(x) \]??\(P(x)\) 某个多项式，用于修补低次项。
??变形：
\[\begin{aligned}A(x)&=F(x)A(x)+P(x)\\\Rightarrow~~~~A(x)&=\frac{P(x)}{Q(x)}~~~~\text{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\not|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)\)，代入变形：
\[\begin{aligned}A(x)&=\frac{P(x)Q(-x)}{R(x^2)}\\\Rightarrow A(x)&=\frac{E(x^2)}{R(x^2)}+x\frac{O(x^2)}{R(x^2)}~~~~\text{let }\begin{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^i\end{cases}\end{aligned} \]??我们要求的只是 \([x^n]A(x)\) 而非整个 \(A(x)\)，所以只需要根据 \(n\) 的奇偶性递归到其中一边求解。复杂度仍然是 \(\mathcal O(m\log m\log n)\)，不过常数会小很多。
??此算法基础上的更多卡常技巧请见 EI 的博客。