FFT / NTT
以 \(\Theta(\mathsf{M}(n)) = \Theta(n \log n)\) 的复杂度，快速计算多项式在 \(n\) 个单位根处的点值，以及通过 \(n\) 个单位根处的点值还原多项式的算法。常用于计算多项式乘法。
由于这个算法的原理在 OI 中是相当板的存在，就不在这里列出了。计算多项式乘法基本只需要用到 NTT，即使模数非 NTT 模数也可以结合 NTT 与中国剩余定理求解。下面给出作者计算多项式乘法的模板：
Code
inline void NTT(int type) {
int n = size(); rev_init(n);
for(int i = 1; i < n; i++) {
if(i < rev[i]) swap(a[i], a[rev[i]]);
}
static int gr[N]; gr[0] = 1;
for(int d = 1; d < n; d <<= 1) {
int gw = qpow(type == 1 ? 3 : invg, (mod - 1) / (d << 1));
for(int i = 1; i < d; i++) {
gr[i] = 1ll * gr[i - 1] * gw % mod;
}
for(int i = 0; i < n; i += d << 1) {
for(int j = 0; j < d; j++) {
int x = a[i + j], y = 1ll * gr[j] * a[i + j + d] % mod;
a[i + j] = add(x, y);
a[i + j + d] = dec(x, y);
}
}
}
if(type == -1) {
for(int i = 0, invn = inv(n); i < n; i++) {
a[i] = 1ll * a[i] * invn % mod;
}
}
}
inline friend Poly operator * (Poly A, Poly B) {
int n = A.size() + B.size() - 1, m = 1;
while(m < n) m <<= 1;
A.resize(m), B.resize(m);
A.NTT(1), B.NTT(1);
for(int i = 0; i < m; i++) {
A[i] = 1ll * A[i] * B[i] % mod;
}
A.NTT(-1), A.resize(n);
return A;
}
Newton 迭代
可以用它实现大部分多项式基本计算（如 Inv, Sqrt, Exp 等），当然更广泛的用途是求解多项式方程。Newton 迭代的原理（即泰勒展开）此处略过，只记录一下其通用的一种使用方式。
记 \(g(f(x)) = 0\) 为一关于 \(f(x)\) 的方程。则我们可以通过以下方式倍增地求出 \(f(x)\)。
标签：基本,int,多项式,rev,NTT,计算,整理,乘法 From： https://www.cnblogs.com/chroneZ/p/18193539