FFT & NTT

优化多项式卷积的思路是老生常谈的了，大体上为三步，系数表达 \(\to\) 点值表达，点值表达做点乘，点值表达 \(\to\) 系数表达。无论 FFT 还是 NTT 只是往里填东西罢了。
系数表达与点值表达

多项式 \(A(x) = \sum_{i = 0}^{n - 1}a_ix^i\) 的系数表达可以理解为一个向量 \((a_0, a_1, \cdots, a_{n - 1})\)。而其点值表达是一个集合 \(\{(x_0, y_0), (x_1, y_1), \cdots, (x_{n - 1}, y_{n- 1})\}\)，其中 \(y_i = A(x_i)\) 且 \(x_i\) 互不相同。
想让后者转化为前者，实际上是在解关于 \(a\) 的方程:

\[\begin{bmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^{n - 1} \\ 1 & x_1 & x_1^2 & \cdots & x_1^{n - 1} \\ 1 & \vdots & \vdots & \ddots & \vdots \\ 1 & x_{n - 1} & x_{n - 1}^2 & \cdots & x_{n - 1}^{n - 1} \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_{n - 1} \end{bmatrix} = \begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_{n - 1} \end{bmatrix}\]

这个系数矩阵是一个范德蒙德矩阵 \(V(x_0, x_1, \cdots, x_{n - 1})\)，行列式算出来是 \(\prod_{j> 1] >> 1) | ((i & 1)  i) swap(a[r], a);    }    for(int nowl = 2; nowl > 1] >> 1) | ((i & 1)  i) swap(a[r], a);    }    for(int nowl = 2; nowl = 1, a = a * a % mod){        if(b & 1) ret = ret * a % mod;    }    return ret;}void ntt(int a[], int op){    for(int i = 0; i < len; ++i) if(r > i) swap(a[r], a);    for(int nowl = 2; nowl sync_with_stdio(0);    cin >> n >> m;    len = 1;    while(len > 1] >> 1) | ((i & 1)