NTT
线性卷积
定义：
\[(f * g)[i] = \sum_{j=0}^{i} f[j] \cdot g[i-j] \]卷积定理：
\[\mathcal{F}(f * g) = \mathcal{F}(f) \cdot \mathcal{F}(g) \]于是，求线性卷积可以转化为，先变换，再直接相乘，最后逆变换。
注意：序列长度须变成N+M-1，对齐2^k。
循环卷积（圆周卷积）
一般用于两个等长序列。
定义：
\[(f * g)[i] = \sum_{j=0}^{N-1} f[j] \cdot g[i-j] \]循环卷积可以通过线性卷积来求解。设 \(B[i]\) 为线性卷积结果，
则循环卷积 \(C[i]=B[i]+B[i+N]\)。
大模数NTT
适用于答案为整数，范围4e18以内，有效弥补FFT在大于1e15后精度不足的缺陷。
__int128常数较大，若答案范围较小(9e8以内)，则用小模数或FFT
struct Polynomial
{
static const ll mod = 4179340454199820289LL; // 998244353LL
vector<ll> z;
vector<int> r;
Polynomial(vector<ll> &a):z(a)
{
int n = a.size();
r.resize(n);
for (int i=0; i<n; i++)
r[i] = (i&1)*(n/2) + r[i/2]/2;
ntt(z, n, 1);
}
ll power(ll a, ll b)
{
ll res = 1;
for(; b; b>>=1, a = (__int128)a * a % mod)
if(b&1) res = (__int128)res * a % mod;
return res;
}
void ntt(vector<ll> &a, int n, int opt)
{
for(int i=0; i<n; i++)
if (r[i]<i) swap(a[i], a[r[i]]);
for(int k=2; k<=n; k*=2)
{
ll gn = power(3, (mod-1)/k);
for(int i=0; i<n; i+=k)
{
ll g = 1;
for(int j=0; j<k/2; j++, g = (__int128)g * gn % mod)
{
ll t = (__int128)a[i+j+k/2] * g % mod;
a[i+j+k/2] = (a[i+j] + mod - t) % mod;
a[i+j] = (a[i+j] + t) % mod;
}
}
}
if (opt == -1)
{
reverse(a.begin()+1, a.end());
ll inv = power(n, mod-2);
for(int i=0; i<n; i++) a[i] = (__int128)a[i] * inv % mod;
}
}
};