由于我的多项式板子实现不够精细，所以这篇博客中的文章都没有放代码。建议找一个精细实现的板子，速度会快很多。
任意模数 NTT
字面意思。
如果不取模，按 OI 常见数据范围来讲两个多项式相乘以后系数不超过 \(10^9\times10^9\times10^5=10^{23}\)，如果我们算出该多项式分别 \(\bmod\) 3 个 NTT 模数下的值，我们就可以通过 CRT 合并计算出模三个模数之积的值，而这样最高精度能达到 \(10^{26}\) 级别，足够应付。但是这种方法一次多项式乘法需要 9 次 DFT，比较慢。下面介绍一下比较常见的优化拆系数 FFT。
众所周知，FFT 中不用取模，只需要结果取一次模就可以了。但是这题最大的系数达到了 \(10^{23}\) 级别，直接 FFT 精度不足。对此我们引出拆系数 FFT。
设 \(bas\) 为一个 \(\sqrt{p}\) 级别的数，\(F(x),G(x)\) 为我们要进行乘法的多项式，那么我们可以把 两个多项式表示成以下形式： \[ F(x)=basA(x)+B(x)\\ G(x)=basC(x)+D(x) \] 其中，\([x^n]A(x)=\lfloor \frac{[x^n]F(x)}{bas} \rfloor\)，\([x^n]B(x)=[x^n]F(x)\bmod bas\)，对于 \(C(x),D(x)\) 同理。这样系数就被降低到了 \(10^5bas^2\) 的级别。那么有 \[ \begin{aligned} F(x)G(x)&=(basA(x)+B(x))(basC(x)+D(x))\\ &=bas^2A(x)C(x)+bas(A(x)D(x)+B(x)C(x))+B(x)D(x) \end{aligned} \] 这样先算出 \(A(x),B(x),C(x),D(x)\) 的点值表示，然后根据乘的系数不同做三次 IDFT，这样一次多项式乘法一共要做 7 次 FFT。
我们发现 DFT 的时候虚部一开始全为 0，可以通过一些方法利用上这里，减少 DFT 次数。
首先我们要明白 DFT 的本质是 \(F(w_n^k)=\sum\limits_{i=0}^nf_iw_n^{ki}\) ，假设我们现在要算出 \(A(x)\) 与 \(B(x)\) 的点值表示。
如果我们知道了一个数组使得 \(F[k]=A(w_n^k)+iB(w_n^k)\)，\(G[k]=A(w_n^k)-iB(w_n^k)\)，那么我们可以通过解方程组的方式知道 \(A(w_n^k)\) 与 \(B(w_n^k)\)。
现在我们尝试推导 \(F\) 与 \(G\) 的关系，通过 DFT 的定义可以知道： \[ \begin{aligned} F[k]&=A(w_n^k)+iB(w_n^k)\\ &=\sum\limits_{j=0}^{n-1}a_iw_n^{kj}+i\sum\limits_{j=0}^nb_jw_n^{kj}\\ &=\sum\limits_{j=0}^{n-1}(a_j+ib_j)w_n^{kj}\\ &=\sum\limits_{j=0}^{n-1}(a_j+ib_j)(\cos(X)+i\sin(X))\\ &=\sum\limits_{j=0}^{n-1}(a_j\cos(X)-b_j\sin(X))+i(b_j\cos(X)+a_j\sin(X))\\ \end{aligned} \] 其中，\(X=\frac{2\pi kj}{n}\)。
同时，我们有 \[ \begin{aligned} G[n-k]&=A(w_n^{n-k})-iB(w_n^{n-k})\\ &=A(w_n^{-k})-iB(w_n^{-k})\\ &=\sum\limits_{j=0}^{n-1}a_iw_n^{-kj}-i\sum\limits_{j=0}^nb_jw_n^{-kj}\\ &=\sum\limits_{j=0}^{n-1}(a_j-ib_j)w_n^{-kj}\\ &=\sum\limits_{j=0}^{n-1}(a_j-ib_j)(\cos(X)-i\sin(X))\\ &=\sum\limits_{j=0}^{n-1}(a_j\cos(X)-b_j\sin(X))-i(b_j\cos(X)+a_j\sin(X))\\ \end{aligned} \] 所以，我们发现 \(F[k]\) 与 \(G[n-k]\) 是共轭的（\(k=0\) 时要特判一下放到 \(G[0]\) 去），所以我们只需要计算出 \(F\)，就可以 \(O(n)\) 计算出 \(G\)。这样只需要 2 次 FFT，就可以计算出四个多项式的点值。
然后考虑 IDFT 部分，这里也可以省一次 FFT。我们正常求 IDFT 的时候最后结果全部都在实部（不明白去看单位根反演），那么如果我们在最开始每个点值都乘上 \(i\)，那么最后出来的结果应该都在虚部，而且数值和放在实部上相等。我们知道 FFT 是一个线性变换，所以我们可以把要求的两个多项式分别放在实部和虚部上，然后 IDFT 之后实部和虚部上就是分别的原多项式了。这样就又省了一次 FFT，一次多项式乘法总共需要 4 次。
实际使用一般设 \(bas\) 为 \(2\) 的次幂，比较方便提取系数。
多项式求逆（乘法逆）
给定 \(n-1\) 次多项式 \(F(x)\) ，求出 \(G(x)\) 使得 \(F(x)G(x)\equiv1\pmod{x^n}\)。
我们要注意乘法逆实际是有无穷项的，只不过我们这里只需要保留前 \(n\) 项。
首先， \(F(x)\) 在系数模质数有逆元的充要条件是 \(F(0)\not=0\) ，即常数项 \([x^0]F(x)\) 不为 \(0\) 。必要性显然因为常数项怎么乘都是 \(0\) ，接下来的构造方式证明了这也是充分条件。
我们先考虑朴素的构造方式，假设我们已知 \(G(x)\) 前 \(m\) 项的值，那么我们算出其与 \(F(x)\) 的乘积，设此时 \(m+1\) 次项的系数为 \(a\) ，那么 \(F(0)[x^{m+1}]G(x)=-a\) ，因为 \(F(0)\not=0\) ，所以 \(F(0)\) 在模 \(p\) 意义下存在逆元，所以 \([x^{m+1}]G(x)=(-a)*(F(0))^{-1}\) ，这样我们每一次可以计算出一项直到 \(n\) 项，复杂度为 \(O(n^2)\) 。
我们考虑已知 \(m\) 项的情况下是否能得到更多项的系数，而不是只推出了后一项。我们考虑倍增，设 \(H(x)\) 为 \(G(x)\bmod x^m\)，即只含有 \(G(x)\) 前 \(m\) 项的多项式。
则我们有 \[ G(x)-H(x)\equiv 0\pmod{x^m} \]
两边同时平方 \[ (G(x)-H(x))^2\equiv0\pmod{x^{2m}} \] 平方使得项度增加了一倍 （ 因为 \(x^m\) 以下的项都为 \(0\)，\(x^m\) 以上的项只能和 \(x^m\) 以上的项相乘，这样指数是大于等于 \(2m\) 的，会被 \(\bmod x^{2m}\) 消掉）。
接下来将括号展开 \[ G^2(x)-2G(x)H(x)+H^2(x)\equiv 0\pmod{x^{2m}} \] 两边同乘 \(F(x)\) \[ F(x)G^2(x)-2F(x)G(x)H(x)+F(x)H^2(x)\equiv 0\pmod{x^{2m}} \] 由定义我们有 \(F(x)G(x)\equiv 1\pmod{x^{2m}}\) \[ G(x)-2H(x)+F(x)H^2(x)\equiv 0\pmod{x^{2m}}\\ G(x)\equiv 2H(x)-F(x)H^2(x)\pmod{x^{2m}} \] 所以我们只需要用三次 NTT 就可以把项数提高一倍。至于递归算还是迭代算，常数应该差距不大，看个人习惯吧。
分治FFT
给定数组 \(g[1],...,g[n-1]\)，求 \(f[0],...,f[n-1]\)，其中 \[ f[i]=\sum\limits_{j=1}^i{f[i-j]g[j]}\\f[0]=1 \] 在模 \(998244353\) 意义下进行
考虑分治，先计算左半边，再计算左对右贡献，最后计算右半边，复杂度 \(O(N\log^2N)\)。
也可以求逆解决，设 \[ F(x)=\sum\limits_{i=0}^{n-1}f[i]x^i\\G(x)=\sum\limits_{i=0}^{n-1}g[i]x^i \] 其中，\(g[0]=0\)
对其卷积（在 \(\bmod x^n\) 意义下进行） \[ F(x)G(x)\sum\limits_{k=0}^{n-1}\sum\limits_{i+j=k}f[i]g[j]x^k\\ F(x)G(x)=\sum\limits_{k=0}^{n-1}f[k]x^k-f[0]\\ F(x)G(x)=F(x)-f[0]\\ F(x)(G(x)-1)=-f[0]\\ F(x)=\frac{f[0]}{1-G(x)} \] （第二行是因为 \(g[0]=0\) ,所以 \(f[0]g[0]=0\)）由于 \(f[0]=1\)，求逆就好了，复杂度\(O(N\log N)\)。
多项式 \(\ln\)
求 \(B(x)\) 使得 \[ B(x)\equiv \ln A(x) \pmod {x^n} \] 设 \[ G(x)=\ln(x) \]
\[ B(x)\equiv G(A(x))\pmod {x^n} \]
两边同时求导得 \[ B'(x)\equiv G'(A(x))A'(x)\pmod {x^n} \]
\[ B'(x)\equiv \frac{A'(x)}{A(x)}\pmod {x^n} \]
\[ B(x) \equiv \int \frac{A'(x)}{A(x)}dx\pmod {x^n} \]
多项式求导，求逆，积分即可
注：
\[ A'(x)=\sum\limits_{i=1}^{n-1}ia_ix^{i-1} \]
\[ \int A(x)dx=\sum\limits_{i=0}^{n-1}\frac{a_{i}}{i+1}x^{i+1} \]
多项式除法和取模
首先，已知 \(n\) 次多项式 \(F(x)=\sum\limits_{i=0}^nf_ix^i\) ，则 \(x^nF(\frac{1}{x})=F_r(x)\) ，其中 \(F_r(x)=\sum\limits_{i=0}^nf_{n-i}x^i\) ，即将 \(F(x)\) 系数翻转后的多项式。
现在，给定 \(n\) 次多项式 \(F(x)\) 和 \(m\) 次多项式 \(G(x)\) \((n>m)\) ，求出 \(n-m\) 次多项式 \(Q(x)\) 和次数小于 \(m\) 的多项式 \(R(x)\) 使得 \(F(x)=G(x)Q(x)+R(x)\)
首先两边同乘 \(x^n\)
则有 \[ x^nF(x)=x^mG(x)x^{n-m}Q(x)+x^{n-m}x^mR(x) \] 将 \(x\) 替换为 \(\frac{1}{x}\) \[ x^nF(\frac{1}{x})=x^mG(\frac{1}{x})x^{n-m+1}Q(\frac{1}{x})+x^{n-m}x^{m-1}R(\frac{1}{x}) \] 套用上面的公式 \[ F_r(x)=G_r(x)Q_r(x)+x^{n-m+1}R_r(x) \] 我们发现 \(Q_r(x)\) 刚好是 \(n-m\) 次多项式所以两边对 \(x^{n-m+1}\) 取模以消掉 \(R_r(x)\) 这一项 \[ F_r(x)\equiv G_r(x)Q_r(x)\pmod{x^{n-m+1}} \] 所以我们只需要求出 \(G_r(x)\) 的逆元，再与 \(F_r(x)\) 相乘就得到了 \(Q_r(x)\) ，再利用定义计算出 \(R(x)\)。复杂度为 \(O(n\log n)\)。