多项式全家桶
多项式求逆
给定多项式 \(f(x)\)，求 \(f^{-1}(x)\)。
首先，易知
\[[x^0]f^{-1}(x)=([x^0]f(x))^{-1} \]假设已经求出 \(f(x)\) 在模 \(x^{\lceil\frac{n}2\rceil}\) 意义下的逆元 \(f_0^{-1}(x)\)。
\[f(x)f_0^{-1}(x)\equiv0\pmod {x^{\lceil\frac{n}2\rceil}}\\ f(x)f^{-1}(x)\equiv0\pmod {x^{\lceil\frac{n}2\rceil}}\\ f^{-1}(x)-f_0^{-1}(x)\equiv0\pmod{x^{\lceil\frac{n}2\rceil}}\\ f^{-2}(x)-2f^{-1}(x)f_0^{-1}(x)+f_0^{-2}(x)\equiv0\pmod{x^n}\\ f^{-1}(x)-2f_0^{-1}(x)+f_0^{-2}(x)f(x)\equiv0\pmod{x^n}\\ f^{-1}(x)\equiv f_0^{-1}(x)(2-f(x)f_0^{-1}(x))\pmod{x^n} \]多项式开方
给定多项式 \(g(x)\)，求多项式 \(f(x)\)，满足 \(f^2(x)=g(x)\)。
首先，易知
\[[x^0]f(x)=\sqrt{[x^0]g(x)} \]假设已经求出 \(g(x)\) 在模 \(x^{\lceil\frac{n}2\rceil}\) 意义下的平方根 \(f_0(x)\)。
\[f_0^2(x)\equiv g(x)\pmod {x^{\lceil\frac{n}2\rceil}}\\ f_0^2(x)-g(x)\equiv0\pmod {x^{\lceil\frac{n}2\rceil}}\\ (f_0^2(x)-g(x))^2\equiv0\pmod{x^n}\\ (f_0^2(x)+g(x))^2\equiv4f_0^2(x)g(x)\pmod{x^n}\\ \left(\dfrac{f_0^2(x)+g(x)}{2f_0(x)}\right)^2\equiv g(x)\pmod{x^n}\\ \dfrac{f_0^2(x)+g(x)}{2f_0(x)}\equiv f(x)\pmod{x^n}\\ f(x)\equiv2^{-1}(f_0(x)+f_0^{-1}(x)g(x))\pmod{x^n} \]多项式除法&取模
给定多项式 \(f(x),g(x)\)，求 \(g(x)\) 除 \(f(x)\) 的商 \(q(x)\) 和余数 \(r(x)\)。
先考虑构造变换
\[f^R(x)=x^{\deg f}f\left(\frac{1}{x}\right) \]容易得到 \(f^R(x)\) 实质为翻转 \(f(x)\) 的系数。
设 \(n\deg f,m=\deg g\)。
将 \(f(x)=q(x)g(x)+r(x)\) 中的 \(x\) 替换为 \(\frac{1}{x}\) 并将两边头乘上 \(x^n\)，得到：
\[\begin{aligned} x^nf\left(\frac{1}{x}\right)&=x^{n-m}q\left(\frac{1}{x}\right)x^mg\left(\frac{1}{x}\right)+x^nq\left(\frac{1}{x}\right)\\ f^R(x)&=q^R(x)g^R(x)+x^{n-m+1}r^R(x) \end{aligned} \]在模 \(x^{n-m+1}\) 下可以忽略 \(r(x)\) 的影响，并且因为 \(\deg q^R(x)=n-m<n-m+1\)，所以不会影响到 \(q^R(x)\)。于是就可以通过逆元算出 \(q^R(x)\)。
算出 \(q(x)\) 后直接带入就可以算出 \(r(x)\)。
多项式对数函数
给定多项式 \(f(x)\)，求多项式 \(g(x)\)，满足 \(g(x)\equiv \ln f(x)\pmod{x^n}\)。
\[\ln f(x)\equiv g(x)\pmod{x^n}\\ (\ln f(x))^\prime f^\prime(x)\equiv g^\prime(x)\pmod{x^n}\\ \dfrac{f^\prime(x)}{f(x)}\equiv g^\prime(x)\pmod{x^n}\\ g(x)\equiv\int f^\prime(x)f^{-1}(x)\,dx \]多项式指数函数
给定多项式 \(f(x)\)，求多项式 \(g(x)\)，满足 \(g(x)\equiv e^{f(x)}\pmod{x^n}\)。
设函数 \(h(g(x))=\ln g(x)-f(x)\)，已求出模 \(x^{\lceil\frac{n}2\rceil}\) 意义下的答案 \(g_0(x)\)，则有
\[g(x)\equiv g_0(x)-\dfrac{h(g_0(x))}{h^\prime(g_0(x))}\pmod{x^n}\\ g(x)\equiv g_0(x)-\dfrac{\ln g_0(x)-f(x)}{(\ln g_0(x)-f(x))^\prime}\pmod{x^n}\\ g(x)\equiv g_0(x)-\dfrac{\ln g_0(x)-f(x)}{\dfrac{1}{g_0(x)}}\pmod{x^n}\\ g(x)\equiv g_0(x)(1-\ln g_0(x)+f(x))\pmod{x^n}\\ \]多项式多点求值
给定多项式 \(f(x)\) 和 \(n\) 个数 \(x_1,x_2,\cdots,x_n\)，求 \(f(x_1),f(x_2),\cdots,f(x_n)\)。
考虑使用分治，将给定的点分为两部分
\[\begin{aligned} X_0&=\{x_1,x_2,\cdots,x_{\lfloor\frac{n}2\rfloor}\}\\ X_1&=\{x_{\lfloor\frac{n}2\rfloor+1},x_{\lfloor\frac{n}2\rfloor+2},\cdots,x_n\} \end{aligned} \]构造函数
\[g_0(x)=\prod_{x_i\in X_0}(x-x_i) \]则有 \(\forall x_i\in X_0,g_0(x_i)=0\)。
考虑将 \(f(x)\) 表示为 \(q(x)g_0(x)+f_0(x)\)，即
\[f_0(x)\equiv f(x)\pmod{g_0(x)} \]则有 \(\forall x_i\in X_0,f(x_i)=q(x_i)g_0(x_i)+f_0(x_i)=f_0(x_i)\)。于是问题规模减半，可以递归处理。
对于 \(X_1\) 同理。
时间复杂度
\[\begin{aligned} T(n)&=2T\left(\frac{n}2\right)+O(n\log n)\\ &=O(n\log^2n) \end{aligned} \]多项式快速插值
多项式平移
多项式连续平移
给定 \(n\) 次的多项式 \(f(x)\) 的 \(n+1\) 个点值 \(f(0),f(1),\cdots,f(n)\) 和一个常数 \(c\)，求 \(f(c),f(c+1),\cdots,f(n+c)\)。
虽然可以暴力插值+平移+求值，但两只 \(\log\) 不够优美，且难写，所以考虑用另一种做法。
考虑拉格朗日插值公式
\[\begin{aligned} f(x)&=\sum_{i=0}^ny_i\prod_{j\not=i}\frac{x-j}{i-j}\\ &=\sum_{i=0}^ny_i\frac{\frac{x!}{(x-n-1)!(x-i)}}{(-1)^{n-i}(i-1)!(n-i)!}\\ &=\frac{x!}{(x-n-1)!}\sum_{i=0}^n\frac{(-1)^{n-i}y_i}{(i-1)!(n-i)!(x-i)} \end{aligned} \]注意到后面的式子长得像卷积形式，所以考虑构造 \(A*B=C\)，满足
\[[x^{n+1+t}]C=\sum_{i=0}^n\frac{(-1)^{n-i}y_i}{(i-1)!(n-i)!(c+t-i)} \]令
\[\begin{aligned} \lbrack x^i\rbrack A&=\frac{(-1)^{n-i}y_i}{(i-1)!(n-i)!}\\ [x^i]B&=\frac{1}{i+c-n-1} \end{aligned} \]则有
\[\begin{aligned} \lbrack x^{n+1+t}\rbrack C&=\sum_{i=0}^{n+t+1}[x^i]A\times[x^{n+t+1-i}]B\\ &=\sum_{i=0}^{n+t+1}\frac{(-1)^{n-i}y_i}{(i-1)!(n-i)!}\times\frac{1}{t-i+c}\\ \end{aligned} \]所以有
\[f(c+t)=\frac{x!}{(x-n-1)!}[x^{n+1+t}]C \]