多项式乘法
存在多项式 \(F(z)=\sum_{i=0}^na_iz^i,G(z)=\sum_{i=0}^mb_iz^i\)，我们定义多项式乘法：
\[F(z)*G(z)=\sum_i\sum_ja_ib_jz^{i+j} \]多项式的点值表达
一个 \(n\) 次函数可以用平面上的 \(n+1\) 个点来表达。
所以我们可以把一个 \(n\) 次多项式从 系数表达 转化成 \(n+1\) 个点来表达，这一步也叫 求值。
然后如果 \(F(z)\) 过 \((x_1,y_1)\)，\(G(z)\) 过 \((x_1,y_2)\)，那么 \((F*G)(x_1)=y_1y_2\)。
所以我们只需要在 \(F,G\) 上各寻找 \(\deg F+\deg G+1\) 个点即可确定 \(F*G\)。
我们变成了 用系数找出点值表达 和 用点值表达表达出系数。
FFT
FFT 可以在 \(O(n\log n)\) 时间复杂度内解决多项式乘法。
DFT
我们先考虑如何找出 \(n+m+1\) 个点值。
前置知识：单位根
单位根 / \(n\) 次单位根：即 \(n\) 次幂为 \(1\) 的复数，用 \(w_n\) 表示
显然 \(n\) 次单位根共\(n\)个，写作\(w^k_{n}\) 的形式
根据 复数乘法模长相乘，幅角相加的法则，发现单位根只存在于半径为\(1\)的单位圆上
且 \(n\) 次单位根将此单位圆 \(n\) 等分
然后单位根有有如下性质：
- \(w_0^n=1\)
- \(w^{i}_nw^j_n=w^{i+j}_n\)
- \(w^{ak}_{an}=w^{k}_{n}\)
- \(w^{k+\frac n2}_n=-w^{k}_n(n\equiv 0(\bmod 2))\)
我们考虑一个 \(n\) 项多项式 \(F(z)=\sum_{i=0}^{n-1}a_iz^i\)，然后我们把 \(n\) 补成 \(2\) 的次幂，所以可以平均分开。
得到：
\[F(z)=\sum_{k=0}^{(n-1)/2}a_{2k}z^{2k}+a_{2k+1}z^{2k+1} \]设 \(FL(z)=\sum_{i=0}^{(n-1)/2}a_{2i}z^i,FR(z)=\sum_{i=0}^{(n-1)/2}a_{2i+1}z^i\)。
显然我们可以发现：
\[F(z)=FL(z^2)+zFR(z^2) \]我们代入一个 \(w^k_n,w^{k+\frac n 2}_n(k<\frac n 2)\)，得到：
\[\begin{aligned} F(w^k_n)&=FL(w^{k}_{n/2})+w^{k}_nFR(w^k_{n/2})\\ F(w^{k+n/2}_n)&=FL(w^k_{n/2})+w^{k+n/2}_nFR(w^k_{n/2})\\ F(w^{k+n/2}_n)&=FL(w^k_{n/2})-w^{k}_nFR(w^k_{n/2})\\ \end{aligned} \]所以如果我们只需要知道 \(FL,FR\) 在 \(w^0_{n/2},w^1_{n/2},w^2_{n/2},\cdots w^{n/2-1}_{n/2},\) 处的点值表达即可，然后可以 \(O(n)\) 的得到 \(F(z)\) 在 \(w^0_{n},\cdots w^{n-1}_n\) 处的点值。
然后我们分治下去即可，时间复杂度 \(T(n)=2T(\frac n 2)+O(n)=O(n\log n)\)。
然后我们考虑点值转为系数表达。
IDFT
我们现在得到了一大堆点值，现在要把他转化成系数。
结论是我们用 \(w^{-1}_n\) 代替 \(w^1_n\) 做上面的部分然后除以 \(n\) 即可。
证明：我们设 \(G=\text{DFT}(F)\)，那么我们知道
\[G_k=\sum_{i=0}^{n-1}F_i(w^k_n)^i \]我们需要证明：
\[\begin{aligned} F_k&=\frac 1 n(\sum_{i=0}^{n-1}G_i(w_n^{-k})^i)\\ &=\frac1 n\sum_{i=0}^{n-1}(w^{-k}_n)^i\sum_{j=0}^{n-1}F_j(w^i_n)^j\\ &=\frac1 n\sum_{j=0}^{n-1}F_j\sum_{i=0}^{n-1}w^{i(j-k)}\\ j= k,ans&=\frac {nF_j}{n}=F_k\\ j\not=k,ans_j&=\frac {F_j} n\sum_{i=0}^{n-1}w^{ij}\\ &=\frac {F_j} n\times \frac {1-w^{jn}}{1-w^j}=0\\ \therefore \frac1 n\sum_{j=0}^{n-1}F_j\sum_{i=0}^{n-1}w^{i(j-k)}&=F_k\\ \end{aligned} \]至于邪恶的蝴蝶变换，这个可以自己手玩得到。
破除封建迷信：STL 的 complex 跑的很快，根本不需要手写。
三次变两次
我们设 \(P=F+Gi\)，那么我们得到 \(P^2=F^2-G^2+2FGi\)，这样我们只用做一次 DFT 和一次 IDFT 即可。
三次变两次不掉精度。
MTT
系数过大的情况下，FFT 会有相当程度的精度误差。
我们把 \(F(x),G(x)\) 分别拆成 \(A(x)+cB(x),C(x)+cD(x)\)，然后我们构造函数 \(T(x)=C(x)+D(x)i\)。
然后我们要得到 \(A(x)C(x)+c(A(x)D(x)+B(x)C(x))+c^2B(x)D(x)\)。
然后我们可以用 \(A(x)T(x),B(x)T(x)\) 得到 \(A(x)C(x)+A(x)D(x)i\) 和 \(B(x)C(x)+B(x)D(x)i\)。
然后就能用 \(3\) 次DFT 和 \(2\) 次 IDFT 解决问题。
NTT
就是用 \(g^{(p-1)/n}_n\) 代替 \(w^1_n\)。
多项式牛顿迭代
主要是解决以下问题。
给出函数 \(g(x)\)，求出一个 \(f(x)\)，使得
\[g(f(x))\equiv 0(\bmod x^n) \]
我们递归考虑，假设我们已经知道 \(t(x)\)，使得：
\[g(t(x))\equiv 0(\bmod x^{\lceil \frac n 2\rceil}) \]那么我们知道
\[f(x)-t(x)\equiv 0(\bmod x^{\lceil \frac n 2\rceil}) \]我们考虑将 \(g(x)\) 在 \(t(x)\) 处泰勒展开，我们得到：
\[\begin{aligned} g(f(x))&=\sum_{n\ge 0}\frac {g^{(n)}(t(x))}{n!}(f(x)-t(x))^n\\ g(f(x))&\equiv g(t(x))+g'(t(x))(f(x)-t(x))+\sum_{n\ge 2}\frac {g^{(n)}(t(x))}{n!}(f(x)-t(x))^n(\bmod x^n) \end{aligned} \]后面那一截等于 \(0\)，所以我们知道：
\[\begin{aligned} g(f(x))&\equiv g(t(x))+g'(t(x))(f(x)-t(x))(\bmod x^n)\\ 0&\equiv g(t(x))+g'(t(x))(f(x)-t(x))(\bmod x^n)\\ f(x)&\equiv t(x)-\frac {g(t(x))}{g'(t(x))} \end{aligned} \]然后递推求解即可。
多项式求逆
给定多项式 \(A(x)\)，求解多项式 \(B(x)\),使得 \(A(x)B(x)\equiv 1(\bmod x^n)\)
考虑令 \(G(z)=\frac 1 z-A(x)\)，那么 \(G'(z)=-\frac 1 {z^2}\)，所以我们得到：
\[F(x)=t(x)-\frac {\frac 1 {t(x)}-A(x)}{-\frac 1 {t(x)^2}}=(2-A(x)t(x))t(x) \]多项式开根
给定多项式 \(A(x)\)，求解多项式 \(B(x)\)，使得 \(B^2(x)\equiv A(x)(\bmod x^n)\)
我们考虑令 \(G(z)=z^2-A(x)\),则我们知道 \(G'(z)=2z\)，所以我们知道 \(F(x)=t(x)-\frac {t^2(x)-A(x)}{2t(x)}=\frac {A(x)+t^2(x)}{2t(x)}\)
然后倍增求解即可，时间复杂度 \(T(n)=T(\frac n2)+O(n\log n)=O(n\log n)\)。
多项式 ln
\[\begin{aligned} \ln A(x)&=\int (\ln A(x))'\\&=\int \frac {A'(x)}{A(x)} \end{aligned} \]给定多项式 \(A(x)\)，求解多项式 \(B(x)\)，使得 \(B(x)\equiv \ln A(x)(\bmod x^n)\)
多项式 exp
给定多项式 \(A(x)\)，求解多项式 \(B(x)\)，使得 \(B(x)\equiv \exp A(x)(\bmod x^n)\)
考虑牛顿迭代，设 \(G(z)=\ln z- A(x)\)，则 \(G'(z)=\frac 1 z\)，所以我们得到：
\[\begin{aligned} F(x)=t(x)-\frac {\ln t(x)-A(x)}{\frac 1 {t(x)}}=(1-\ln t(x)-A(x))t(x) \end{aligned} \]倍增求解即可，时间复杂度为 \(O(n\log n)\)。
多项式快速幂
\[\begin{aligned} A^k(x)=\exp (k\ln A(x)) \end{aligned} \]给定多项式 \(A(x)\)，常数 \(k\)，求解多项式 \(B(x)\)，使得 \(B(x)\equiv A^k(x)(\bmod x^n)\)
\(O(n^2)\) 多项式操作
由于 shaber FFT 是高贵的 10 级考点，所以我们如果不想背那个 shaber 东西就用 \(O(n^2)\) 多项式操作吧。
可能在集合幂级数上可以使用。
多项式乘法
直接做即可。
多项式求逆
\[\begin{aligned} b_0&=\frac1 {a_0}\\ \sum_{i=0}^na_ib_{n-i}&=0\\ b_n&=-\frac 1 {a_0}\sum_{i=1}^na_ib_{n-i} \end{aligned} \]多项式 \(\ln\)
\[\begin{aligned} \ln A(x)&=\int (\ln A(x))'\\&=\int \frac {A'(x)}{A(x)} \end{aligned} \]多项式 \(\exp\)
\[\begin{aligned} B(x)&=\exp A(x)\\ B(x)'&=(\exp A(x))A'(x)\\ B(x)'&=B(x)A'(x) \end{aligned} \]两遍提取系数即可。
多项式快速幂
\[\begin{aligned} B(x)&=A^k(x)\\ B(x)'&=kA^{k-1}(x)A'(x)\\ B(x)'A(x)&=kB(x)A'(x) \end{aligned} \]提取系数递推即可。
Boston-mori 算法
对于两个 \(k\) 次多项式 \(F(z),G(z)\)，我们可以在 \(O(k\log k\log n)\) 的时间复杂度内求出
\[[z^n]\frac {F(z)}{G(z)} \]\[\begin{aligned} Ans=[z^n]\frac {F(z)G(-z)}{G(z)G(-z)}\\ =[z^n]\frac {c_{even}(z^2)+xc_{odd}(z^2)}{v(z^2)}\\ \end{aligned} \]如果 \(n=1(\bmod 2)\) 的话，\(Ans=[z^{n/2}]\frac {c_{odd}(z)}{v(z)}\)。
否则 \(Ans=[z^{n/2}]\frac {c_{even}(z)}{v(z)}\)。
所以我们只需要 \(O(\log n)\) 次多项式乘法即可。
标签：frac,多项式,sum,笔记,aligned,bmod,模板,equiv From： https://www.cnblogs.com/Nityacke/p/18172039