多项式卷积与DFT与FFT

之所以取这个标题。。。
是因为我自己以前只认为FFT只是一种精妙的构造。
并没能意识到这只是信息学中庞大多项式理论中的 ${\rm the\ tip \ of \ the \ iceberg}$
查漏补缺~~格物致知~~。

多项式：
多项式可以是一个形式幂级数，也可以是一个多项式函数。
多项式环理论上是指一个对于加减乘封闭的群，实际上常用 $\Z[x]/(f(x))$ 表示在 $\pmod{f(x)}$ 的环境下的加减乘封闭的群。同理 $\Z/(998244353)$ 表示在 $\pmod{998244353}$ 意义下的加减乘封闭的群，他们都是环。
卷积：
强烈推荐阅读WC2018营员交流的LCA的浅谈卷积定理在OI中的应用及扩展
$c_i = \sum_{j\cdot k = i} a_jb_k$
卷积定理：
多项式卷积与DFT与FFT

卷积定理。
上面的PPT同时告诉了我们只要有n次单位元（和一些一般都满足的性质），那么我们就可以将长度为n的循环卷积改为点积。

多项式卷积与DFT与FFT
后文是钻进了线性代数的（XX）中，所以可以不用管了。
只要满足上述方程组的变换矩阵和循环律就可以DFT然后循环卷积变点积。

DFT：我上一栏好像说太多了。
就是变换。
只要有2n个点值（和逆元）就可以支持点乘代替多项式乘法。
只要有n次单位根（和n的逆元）就可以支持点乘代替长度为n的循环卷积。
只要猜出了变换矩阵和有n次单位根（和n的逆元）就可以支持点乘代替长度为n的有循环性的卷积。
不循环的卷积没办法套快速幂，数据范围因为要卡的住人所以会对模数和单位根很不友好。

多维DFT：
首先对于一般的循环卷积：雷打不动 $Trans(a)[i] = \sum_{j=0}^{n} \omega_n^{ij}a[j]$
$a[i] = \frac 1n\sum_{j=0}^n -\omega_n^{ij}tTrans(a)[j]$
对于多个环: $R_1,R_2,R_3...R_n$ 分别有单位根 $\omega_1,\omega_2...\omega_n$
那么对于 $a(x_1, x_2, \dots, x_n) = \sum_{i_1=0}^{n_1-1} \dots \sum_{i_d=0}^{n_d-1} a_{i_1, i_2, \dots, i_d} x_1^{i_1} \dots x_d^{i_d}.$
定义傅里叶变换将 $a$ 变换成 $b = \mathcal{F}(a)$ 为
$b_{k_1, k_2, \dots, k_d} = \sum_{j_1 = 0}^{n_1-1} \dots \sum_{j_d = 0}^{n_d-1} \omega_1^{j_1k_1} \dots \omega_d^{j_dk_d} a_{j_1,j_2,\dots,j_d}.$
其逆变换为
$a_{j_1,j_2,\dots,j_d} = n_1^{-1} n_2^{-1} \dots n_d^{-1} \sum_{k_1 = 0}^{n_1-1} \dots \sum_{k_d = 0}^{n_d-1} \omega_1^{-j_1k_1} \dots \omega_d^{-j_dk_d} b_{k_1, k_2, \dots, k_d}.$

然后就可以做codeforces 1103 E. Radix sum了。

FFT：
$n\log n$ 完成长度为 $2^n$ 的DFT变换，需要 $2^i(0<=i<=n)$ 次单位根，条件比较苛刻但是应用较广？？？因此广为人知（背代码）。

多项式卷积与DFT与FFT

相关推荐