FFT/NTT
板子，就不说了。
分治 FFT
给定序列 \(g_{1\dots n - 1}\)，求序列 \(f_{0\dots n - 1}\)。其中 \(f_i=\sum_{j=1}^if_{i-j}g_j\)，边界为 \(f_0=1\)。
Solution 1
朴素地做是 \(\mathcal{O}(n^2)\) 的。观察到后面的项依赖前面的项。于是我们可以考虑用 cdq 分治实现。
具体地
-
若 \(l=r\)，结束递归。
-
递归求解 \([l,mid]\)
-
计算 \([l,mid]\) 对 \([mid+1,r]\) 的影响。
-
求解 \([mid+1,r]\)。
\([l,mid]\) 对 \(f_i, i\in [mid+1,r]\) 的影响为 \(\sum _{j=l}^{mid} f_jg_{i-j}\)。
观察到这是一个卷积的形式。于是我们令 \(a_i=f_{l+i}\)，\(b_i=g_i\)，则计算出 \(c=a\ast b\)，\([l,mid]\) 对 \([mid+1,r]\) 中 \(i\) 的贡献为 \(c_{i-l}\)。
时间复杂度 \(\mathcal{O}(n\log^2 n)\)。
Solution 2
令 \(F(x),g(x)\) 为 \(f,g\) 的生成函数。
则 \(F(x)G(x)=\sum_{i=0}^{+\infty} x^i\sum_{j+k=i}f_jg_k=F(x)-1\)。
故 \(F(x)=\frac{1}{1-G(x)}\)。
时间复杂度 \(\mathcal{O}(n\log n)\)。
任意模数多项式乘法（MTT）
Method 1：三模 NTT
由于 \(p\leq 10^9+9\)，\(n,m\leq 10^5\)，故最大的数可以到 \(p^2\cdot n=10^{23}\)（默认 \(n,m\) 同阶）级，故我们需要选取三个大素数使得 \(p_1p_2p_3\gt 10^{23}\)。
一般选取 \(p_1=496,762,049\)，\(p_2=998,422,353\)，\(p_3=1,004,535,809\)，它们都存在原根 \(G=3\)。我们求出后可以利用 CRT 求出答案（需要利用 __int128）。
不过这个方法常数很大（需要做 \(9\) 次 NTT/INTT）。
Method 2：拆系数 FFT
我们设 \(c\) 是一个 \(\sqrt{p}\) 左右级别的整数。那么我们可以将 \(F(x)\) 拆成 \(A(x)+c\cdot B(x)\)。其中 \([x^i]A(x)=[x^i]F(x)\bmod c\)，\(\displaystyle [x^i]B(x)=\lfloor\frac{[x^i]F(x)}{c}\rfloor\)。这样可以将系数降到 \(10^5\) 级别。
于是设 \(F(x)=A(x)+c\cdot B(x)\)，\(G(x)=C(x)+c\cdot D(x)\)，于是 \(F(x)G(x)=A(x)C(x)+c\left[A(x)D(x)+B(x)C(x)\right]+c^2\cdot B(x)D(x)\)。
设 \(T(x)=C(x)+D(x)\cdot \mathrm{i}\)，其中 \(\mathrm i\) 为复数单位。于是我们可以在 \(A(x)\cdot T(x)\) 中找到 \(A(x)C(x)\) 和 \(A(x)D(x)\)，在 \(B(x)\cdot T(x)\) 中找到 \(B(x)C(x)\) 和 \(B(x)D(x)\)。
于是我们需要：
-
对 \(A(x)\)，\(B(x)\)，\(T(x)\) 做 DFT
-
对 \(A(x)T(x)\)，\(B(x)T(x)\) 做 IDFT
共五次 FFT。常数是三模 NTT 的一半左右。
多项式乘法逆
考虑倍增。假设我们求出了 \(G_0(x)\) 使得 \(F(x)\cdot G_0(x)\equiv 1\pmod {x^n}\)，我们考虑求出 \(G(x)\) 使得 \(F(x)\cdot G(x)\equiv 1\pmod {x^{2n}}\)。
由于 \(F(x)\cdot G(x)\equiv 1\pmod {x^{\textcolor{red}{2n}}}\)，所以必有 \(F(x)\cdot G(x)\equiv 1\pmod {x^{\textcolor{red}{n}}}\)。于是我们有
\[F(x)\cdot G(x)\equiv F(x)\cdot G_0(x)\pmod {x^n} \]则 \(F(x)\) 可消去，得到
\[G(x)-G_0(x)\equiv 0\pmod {x^n} \]\[G^2(x)-2G(x)G_0(x)+G_0^2(x)\equiv 0\pmod {x^{2n}} \]考虑到 \(F(x)\cdot G(x)\equiv 1\)，则两边同乘 \(F(x)\)
\[G(x)-2G_0(x)+F(x)G_0^2(x)\equiv 0\pmod {x^{2n}} \]则 \(G(x)\equiv G_0(x)(2-F(x)G(x))\pmod {x^{2n}}\)。于是可以倍增求出。
我们有 \(T(n)=T(\frac{n}{2})+\mathcal{O}(n\log n)\)，则时间复杂度为 \(\mathcal{O}(n\log n)\)。（但是你猜猜常数有多少？）
任意模数多项式乘法逆
把 NTT 换成任意模数的即可。
多项式对数函数
对 \(G(x)\equiv \ln F(x) \pmod {x^n}\) 的两边求导，得
\[G'(x)\equiv \frac{F'(x)}{F(x)} \pmod {x^n} \]于是
\[G(x)\equiv \int \frac{F'(x)}{F(x)} \pmod {x^n} \]时间复杂度 \(\mathcal{O}(n\log n)\)。
多项式 Newton 迭代
给定多项式 \(g(x)\)，若已知 \(f(x)\) 满足 \(g(f(x))=0\)，求出模 \(x^n\) 意义下的 \(f(x)\)。
考虑倍增。
边界是 \(n=1\)，此时需要单独解出 \([x^0]g(f(x))=0\) 的解。
设已经得到了模 \(x^{\lceil\frac{x}{2}\rceil}\) 下的解 \(f_0(x)\)。
对 \(g(x)\) 在 \(f_0(x)\) 处进行 Taylor 展开，其中 \(g^{(i)}\) 表示对 \(g\) 求 \(i\) 阶导数，规定 \(g^{(0)}=g\)。
\[\sum_{i=0}^{+\infty }\frac{g^{(i)}(f_0(x))}{i!} (f(x)-f_0(x))^i\equiv 0\pmod {x^n} \]\(f(x)-f_0(x)\) 最低的非零项系数为 \(x^{\lceil\frac{n}{2}\rceil}\)。那么当 \(i\geq 2\) 时，\(2\lceil\frac{n}{2}\rceil\geq n\)，在模 \(x^n\) 意义下为 \(0\)，亦即，\(\forall i\geq 2\)，都有 $ (f(x)-f_0(x))^i\equiv 0\pmod {x^n}$。
那么就很好做了。上式可以化简成
\[g(f_0(x))+g'(f_0(x))\cdot (f(x)-f_0(x))\equiv 0\pmod {x^n} \]于是不难解得
\[f(x)\equiv f_0(x)-\frac{g(f_0(x))}{g'(f_0(x))}\pmod {x^n} \]那么我们不妨再来回顾一下多项式求逆。
给定 \(h(x)\)，求出 \(f(x)\)，使得 \(h(x)\cdot f(x)\equiv 1\pmod {x^n}\)。
观察牛顿迭代的形式
给定多项式 \(g(x)\)，若已知 \(f(x)\) 满足 \(g(f(x))=0\)，求出模 \(x^n\) 意义下的 \(f(x)\)。
我们要让左边是一个多项式，右边是 \(0\)。我们考虑变一下形。
\[h(x)\cdot f(x)\equiv 1\pmod {x^n} \]\[h(x)\cdot f(x)-1\equiv 0\pmod {x^n} \]\[h(x)-\frac{1}{f(x)}\equiv 0\pmod {x^n} \]即
\[\frac{1}{f(x)}-h(x)\equiv 0\pmod {x^n} \]那么令 \(g(f(x))=\frac{1}{f(x)}-h(x)\)，我们得到
\[\begin{aligned} f(x)&\equiv f_0(x)-\frac{g(f_0(x))}{g'(f_0(x))} \pmod {x^n}\\ &\equiv f_0(x)-\frac{\frac{1}{f_0(x)}-h(x)}{-\frac{1}{f_0^2(x)}} \pmod {x^n}\\ &\equiv f_0(x)(2-f_0(x)h(x)) \pmod {x^n} \end{aligned} \]注意 \(g(f_0(x))\) 的主元是 \(f_0\)。不妨令 \(f_0=t\)，则有 \(g(t)=\frac{1}{t}-h(x)\)，这里 \(h(x)\) 当作常数，故 \(g'(t)=-\frac{1}{t^2}\)。
多项式 exp
给定 \(h(x)\)，求出 \(f(x)\) 使得 \(\exp(h(x))\equiv f(x)\pmod {x^n}\)。
考虑变换形式。上式即
\[h(x)\equiv \ln f(x)\pmod {x^n} \]故 \(\ln f(x)-h(x)\equiv 0\pmod {x^n}\)。那么令 \(g(f(x))=\ln f(x)-h(x)\)。
应用 Newton 迭代的结论，我们得到
\[\begin{aligned} f(x)&\equiv f_0(x)-\frac{g(f_0(x))}{g'(f_0(x))}\pmod {x^n} \\ &\equiv f_0(x)-\frac{\ln f(x)-h(x)}{\frac{1}{f_0(x)}}\pmod {x^n} \\ &\equiv f_0(x)(1-\ln f(x)+h(x))\pmod {x^n} \end{aligned} \]\(T(n)=T(\frac{n}{2})+\mathcal{O}(n\log n)\)，所以时间复杂度为 \(\mathcal{O}(n\log n)\)。但是常数应该很大。
多项式开根
给定 \(h(x)\)，求出 \(f(x)\) 使得 \(\sqrt{h(x)}\equiv f(x)\pmod {x^n}\)。
上式即 \(f^2(x)-h(x)\equiv 0\pmod {x^n}\)。于是令 \(g(f(x))=f^2(x)-h(x)\)。
\[\begin{aligned} f(x)&\equiv f_0(x)-\frac{g(f_0(x))}{g'(f_0(x))}\pmod {x^n} \\ &\equiv f_0(x)-\frac{f_0^2(x)-h(x)}{2f_0(x)}\pmod {x^n} \\ &\equiv \frac{f_0^2(x)+h(x)}{2f_0(x)}\pmod {x^n} \end{aligned} \]\(T(n)=T(\frac{n}{2})+\mathcal{O}(n\log n)\)，时间复杂度 \(\mathcal{O}(n\log n)\)。（可能需要求解二次同余。）
多项式快速幂
事实上，存在 \(\mathcal{O}(n\log n\log k)\) 的快速幂做法。