说是要省选后来学多项式的，结果一直咕咕咕到现在，长文警告。
多项式定义：
(f(x) = sumlimits_{k = 0}^na_kx^k)
((a_n != 0))
卷积：
对于数组(a,b),令：
(c_k = sumlimits_{i + j = k}a_ib_j = sumlimits_{i = 0}^{k} a_i b_{k = i} = sum_{j = 0}^ka_{k - j}b_j)
则(c)为(a)和(b)的卷积。
多项式乘法：
(f(x) = sumlimits_{k = 0}^na_kx^k)
(g(x) = sumlimits_{k = 0}^nb_kx^k)
(f(x)g(x) = sumlimits_{k = 0}^nc_kx^k)
(c)为(a)和(b)的卷积。
显然：直接计算的时间复杂度为(O(nm))
多项式点值表示：
(LaTex)学艺不精
挂个图。
对一个(n)次多项式和(m)次多项式乘法来说(O(n + m))
单位根。
多项式(x^n - 1)的根被称作(n)次单位根。
设(w_n = e^{frac{2pi i}{n}} = cos(x) + isin(x))
容易验证(w_n^n = 1)
对于质数(p = kn + 1,设w_n = g^{frac{p - 1}{n}}，g为膜p的原根,显然w_n^n = 1)
在上述两种情况下，(1,w_n,w_n^2......w_n^{n - 1})为(n)个不同的(n)次单位根
DFT的定义：
(f(x) = sumlimits_{k = 0}^{n - 1}a_kx^k)
(DFT(a) = {f(1)，f(w_n),f(w_n^1)......f(w_n^{n - 1})})
称为(a)的离散傅里叶变换。
从而得到了(f(x))的一个点值表示。
IDFT的定义：
(DFT)的逆变换称为(IDFT)或(DFT^{-1})，(IDFT)是把点值表示变换成系数表示。
容易证明：只要将(DFT)中的(w_n)换为(w_n^{-1})并将结果除(n)，形象的说(g(x) = sumlimits_{k = 0}^{n - 1}f(w_n^k)x^k)，则有(a = DFT^-1(DFT(a)) = frac{1}{n}(g(1),g(w_n^{-1}).......g(w_n^{-(n- 1)})))
循环卷积：
对大小为(n)的数组(a,b)，令：
(c_k = sumlimits_{(i + j) mod n = k}a_ib_j = sumlimits_{i + j =
k}a_ib_j + sumlimits_{i + j = n + k}a_ib_j)
此时(c)为(a)和(b)的循环卷积，用(a⊗b)表示
卷积定理：
设(f(x) = sumlimits_{k = 0}^{n - 1}a_kx^k)
(g(x) = sumlimits_{k = 0}^{n - 1}b_kx^k)
(h(x) = sumlimits_{k = 0}^{n - 1}c_kx^k)
由于有((w_n^s)^n = 1)
所以：
(f(w_n^s)g(w_n^s) = sumlimits_{k = 0}^{n - 1}(sumlimits_{i + j = k}a_ib_j + sumlimits_{i + j = n + k}a_ib_j)(w_n^s)^k = h(w_n^s))
借助(DFT和IDFT)
有(IDFT(DFT(a) ◦ DFT(b)) = a⊗b)
(◦)是逐元素相乘。
FFT综述
快速傅里叶变换，或FFT，是快速计算(DFT)的方法，其时间复杂度仅为(O(nlogn))
在(OI)中，通常要求实现(n = 2^k)的FFT，如果要计算(a)和(b)的卷积(c)，可以取(n)为不小于(c)的大小的最小的(2^k),将(a)和(b)的大小扩充到(n)再计算。
对于膜质数(p),若(p = k * 2^l + 1)，若(n = 2 ^ k and k <= l)则(n次单位根)在(Fp),从而可以计算(DFT)
一个常见的(p)
(998244353 = 7 * 17 * 2^{23} + 1)
相应原根可取(3)，注意(2^{23} < 10^7)
设(n为2^k)
(f(x) = sumlimits_{k = 0}^{n - 1}a_kx^k)
(f_0(x) = sumlimits_{k = 0}^{(n / 2) - 1}a_{2k}x^k)
(f_1(x) = sumlimits_{k = 0}^{(n / 2) - 1}a_{2k + 1}x^k)
有(f(x) = f_0(x^2) + xf_1(x^2))
对于 (n = 2^k)，可以将所有下标视为 k 位二进制数。将下标根据
是否小于 (frac{n}{2})划分成两部分是根据最高位进行划分，而根据奇偶
性划分成两部分是根据最低位进行划分。对于前者，可以自然地将递归树展开。而对于后者，只要将所有下标的二进制位翻转，就可以转化为前者的情况
先去写点(FFT)的应用。