前置知识
形式幂级数
对于一个多项式 \(\sum_{i=0}^{\infty}a_ix^i\)，如果我们只关心它的各项系数 \(\{a_0,a_1...\}\)，而并不关心 \(x\) 的值以及其收敛或发散的问题，就可以说其是关于 \(x\) 的形式幂级数。
牛顿迭代
对于一个已知的多项式 \(F\)，求一个多项式 \(A\)，使得 \(F(A)=0\) 在模 \(x^n\) 意义下成立，其中 \(F,A\) 都是形式幂级数。
牛顿迭代是这样的，假设我们已经求得了在模 \(x^{\frac{n}{2}}\) 下的解 \(A_0\)，那么可以把 \(F(A)\) 在 \(A_0\) 处泰勒展开，再模掉 \(x^n\)，就有 \(F(A)=F(A_0)+F'(A_0)(A-A_0)\)，然后就可以通过解方程求的在模 \(x^n\) 意义下的 \(A\)。
运算
加减法
就是多项式对应项相加减。即 \(C_ix^i=(A_i+B_i)x^i\)。复杂度 \(O(n)\)。
乘法（卷积）
多项式的乘法本质上是求 \(C_ix^i=\sum_{j+k=i}A_jB_kx^i\)。可以使用 FFT 或者 NTT 解决。复杂度 \(O(n\log n)\)。
求导
对于一个单项式 \(kx^n\) 求导，其值是 \(knx^{n-1}\)，而对于多项式的求导，本质上是把各个单项式求导之后再加起来。即 \(C_ix^i=(i+1)A_{i+1}x^i\)。复杂度 \(O(n)\)。
有两个在多项式中常见的求导公式：\((\ln x)'=\frac{1}{x},(e^x)'=e^x\)。
特别的，复合函数也可以求导，\((F(G))'=F'(G)\times G'\)。
积分
积分是求导的逆运算，在求导中，有 \(kx^n\rightarrow knx^{n-1}\)，那么积分里面就有 \(kx^n\rightarrow\frac{k}{n+1}x^{n+1}\) 。而对于多项式的积分，也是把各个单项式求导之后再加起来，即 \(C_ix^i=\frac{A_{i-1}}{i}x^i\)。复杂度 \(O(n)\)。
翻转
对于一个 \(n\) 次多项式 \(A(x)=\sum_{i=0}^n a_ix^i\)，将它变成 \(\sum_{i=0}^n a_{n-i}x^i\)，就称之为翻转，记作 \(A^R(x)\)，不难发现本质上 \(A^R(x)=A(\frac{1}{x})\times x^n\)。复杂度 \(O(n)\)。
求逆
对于一个多项式 \(A(x)\)，求出一个多项式 \(A^{-1}(x)\)，使得 \(A(x)\times A^{-1}(x)\equiv 1~(~{\rm mod}~x^{n})\)。
考虑使用牛顿迭代，设 \(B(x)=A^{-1}(x)\)，那么就有 \(\frac{1}{B(x)}-A(x)\equiv 0~(~{\rm mod}~x^{n})\) 。假设我们现在求得了在模 \(x^{\frac{n}{2}}\) 意义下的解 \(B_0(x)\)，那么就有 \(\frac{1}{B(x)}=\frac{1}{B_0(x)}+(\frac{1}{B_0(x)})'(B(x)-B_0(x))\)，我们知道 \((\frac{1}{B_0(x)})'=-\frac{1}{B_0^2(x)}\)，那么把 \(\frac{1}{B(x)}-A(x)\equiv 0~(~{\rm mod}~x^{n})\) 中的 \(\frac{1}{B(x)}\) 换成上面右边的那一坨，然后稍加整理一下就有 \(B(x)\equiv 2B_0(x)-A(x)B_0^2(x)~(~{\rm mod}~x^n)\) 。直接这么倍增处理即可，复杂度是 \(O(n\log n)\) 的。因为相对于最后一次来说，前面的若干次可以忽略不计。
除法和取模
\(A(x)=B(x)\times C(x)+D(x)\)，其中 \(A(x)\) 是 \(n\) 次多项式，\(B(x)\) 是 \(m\) 次多项式，\(m<n\)，给出 \(A(x),B(x)\)，求 \(C(x),D(x)\)。
显然，\(C(x)\) 的次数是 \(n-m\)，\(D(x)\) 的次数最大是 \(m-1\)，就把它看做是 \(m-1\) 项，高位不足就补零。
先换元，把等式两边的 \(x\) 换做 \(\frac{1}{x}\)，然后再在两边同时乘上 \(x^n\)，就有 \(A(\frac{1}{x})\times x^n=B(\frac{1}{x})\times x^{m}\times C(\frac{1}{x}) \times x^{n-m}+D(\frac{1}{x})\times x^{m-1}\times x^{n-m+1}\)，根据上述的翻转式子，就是 \(A^R(x)=B^R(x)\times C^R(x)+D^R(x)\times x^{n-m+1}\) 。前面已经说了 \(C(x)\) 的次数是 \(n-m\)，那么等式模去 \(x^{n-m+1}\) 并不会对 \(C(x)\) 有任何损失，所以就有 \(A^R(x)\equiv B^R(x)\times C^R(x)~({\rm mod}~x^{n-m+1})\)，对 \(B^R(x)\) 求个逆元乘上就可以得到 \(C^R(x)\)，翻转一下就是 \(C(x)\)，然后就可以通过 \(A(x)-B(x)\times C(x)\) 得到 \(D(x)\)。复杂度 \(O(n\log n)\)。
ln 和 exp
因为积分是求导的逆运算，所以一个多项式先求导再积分，多项式不变。
那么对于 ln，就可以先求导再积分来求。即 \(\ln F(x)=\int_0^n(\ln F(x))'~{\rm dx}\)，前面已经提到了复合函数求导，所以就有 \(\ln F(x)=\int_0^n\frac{F'(x)}{F(x)}~{\rm dx}\) 。复杂度 \(O(n \log n)\)。
对于 exp，它是 ln 的逆运算，考虑用牛顿迭代求。设 \(B(x)=e^{A(x)}\)，那么就有 \(\ln B(x)-A(x)=0\)，假设我们现在求得了在模 \(x^{\frac{n}{2}}\) 意义下的解 \(B_0(x)\)，那么就有 \(\ln B(x)=\ln B_0(x)+\ln'B_0(x)(B(x)-B_0(x))\)，上文已有 \(ln'B_0(x)=\frac{1}{B_0(x)}\)，把这个 \(\ln B(x)\) 带回原式中去，整理一下就有 \(B(x)\equiv B_0(x)(A(x)+1-\ln B_0(x))~(~{\rm mod}~x^n)\)。直接倍增求即可，复杂度也是 \(O(n\log n)\)。
开根
对于一个多项式 \(A(x)\)，求出一个 \(B(x)\)，使得 \(B^2(x)\equiv A(x)~(~{\rm mod}~x^n)\)。
仍然可以使用牛顿迭代法求，假设我们现在求得了在模 \(x^{\frac{n}{2}}\) 意义下的解 \(B_0(x)\)，那么就有 \(B^2(x)=B_0^2(x)+(B_0^2(x))'(B(x)-B_0(x))\)。类似的，整理之后就有 \(B(x)\equiv \frac{A(x)}{2B_0(x)}+\frac{B_0(x)}{2}~(~{\rm mod}~x^n)\) 。复杂度是 \(O(n \log n)\) 的。
其他东西
分治 FFT
分治 FFT 可以用来干两种事情。
一种是要把一堆多项式要乘起来，如果直接一个一个乘的话复杂度最坏是 \(O(n^2\log n)\) 的，而如果每次对半分，左右分别计算然后再卷积一次，单层的复杂度就是 \(O(n\log n)\) 的，一共 \(O(\log n)\) 层，总复杂度 \(O(n\log^2 n)\)。
还有一种是需要求一个多项式的时候，前面的项对后面的项有影响，那么就可以用 CDQ 分治的思想，先算前面的，然后算前面对后面的贡献，最后再算后面的，复杂度 \(O(n \log^2 n)\)。
任意模数 NTT
有两种方法，三模数 NTT 和 拆系数 MTT。
三模数 NTT，就如它的名字，选三个 NTT 模数，分别做一遍 NTT 最后用 CRT 合并。最后 CRT 求出来的一定是精确的值，所以需要保证最终的值在三个 NTT 模数的乘积以内。复杂度是 \(O(n \log n)\)，9 倍常数。
拆系数 MTT，也如它的名字，就是把每个数 \(X\) 拆成 \(AM+B\) 的形式，那么如果有两个多项式 \(AM+B\) 和 \(CM+D\) 相乘，最后的结果就是 \(ACM^2 + (AD+BC)M+BD\)，最后乘出来的结果是 \(M^2{\rm len}\)，一般情况下可以跑 FFT，用 long double 存。复杂度是 \(O(n\log n)\)，7 倍常数。
多点求值
对于一个多项式 \(F\)，给出一些 \(z_i\)，需要求出 \(F(z_i)\) 的值。
对于求出 \(F(z_i)\)，我们可以这么做：次数从高到低扫这个多项式，然后把当前项的一个 \(x\) 展开成 \(z_i\)（即对于 \(ax^k\)，把它展开成 \(ax^{k-1}z_i\)，然后把它累加到 \(x^{k-1}\) 项中去），最后在常数项的那个值就是 \(F(z_i)\)。可以发现，这个过程实际上就是对 \(x-z_i\) 取模。
对于上述问题，有另一种理解方式：设 \(F(z)=A(z)(z-z_i)+B\)，那么当 \(z=z_i\) 时，\(F(z_i)=B\)，所以本质上就是对 \(x-z_i\) 取模。
在自然数集中，有 \(X~{\rm mod}~BC~{\rm mod}~B = X~{\rm mod}~B\)，其实在多项式中也是这样。
所以可以考虑分治。在分治的过程中，把 \(F\) 对 \(\prod_{i=l}^r (x-z_i)\) 取模，最后递归到叶子节点的时候，当前的多项式就只剩下常数项，就是需要求的 \(F(z_i)\)。
考虑发现复杂度，一开始需要求得 \(\prod_{i=l}^r (x-z_i)\) ，分治 FFT 解决。之后需要分治求解，在每一层，多项式的长度都是 \(O({\rm len})\)，所以每层的总长是 \(O(n)\) 的，一共有 \(O(\log n)\) 层。所以总复杂度是 \(O(n \log^2 n)\) ，常数巨大。