神奇的多项式1

FFT

$f(x)=a_0+a_1x+a_2x^2…a_nx^n,g(x)=a_0+a_1x+a_2x^2…a_nx^n$

定义$h(x)=g(x)\times f(x)$ ，小学学习的多项式乘法$n^2$。

工具-复数

定义$n$个复数。将复数坐标系上单位圆分成$n$份。
$e^{ix}=\cos x+i\sin x$。

$w_n^{i}=\cos \frac{2\pi k}{n}+i\sin \frac{2\pi k}{n}$

复数相乘类似向量，并且满足辅角相加，模长相乘。

$w_n^k=w_n^{k+n},w_n^k=-w_n^{k+\frac{n}{2}},w_n^k=w_{\frac{n}{2}}^{\frac{k}{2}},\frac{1}{w_n^k}=w_n^{-k}$

点值表达法

可以转换为点值表达法,朴素暴力转换$n^2$

$(x_0,f(x_0)),(x_1,f(x_1)),(x_2,f(x_2))…(x_{n-1},f(x_{n-1})),$

$(x_0,g(x_0)),(x_1,g(x_1)),(x_2,g(x_2))…(x_{n-1},g(x_{n-1})),$

然后$n$的相乘就可以得到$h(x)$的点值表达了。

有已知$n-1$个点值表示就可以确定$f_n(x)$，显然瓶颈在互相转换的时间复杂度上。

DFT

即转换成点值表达法,考虑使用这些复数当点值。假设$n=2^k$

$h(x)=(a_0+a_2x^2+…a_{n-2}x^{n-2})+(a_1x+a_3x^3+…a_{n-1}x^{n-1})$

设$h_0(x)=(a_0+a_2x^1+…a_{n-2}x^{(n-2)/2}),h_1(x)=(a_1+a_3x^1+…a_{n-1}x^{(n-2)/2})$

$h(x)=h_0(x^2)+xh_1(x^2)$

带入$w_n^k,w_n^{k+\frac{n}{2}}$

$h(w_n^k)=h_0(w_n^{2k})+w_n^kh_1(w_n^{2k})$

$h(w_n^{k+\frac{n}{2}})=h_0(w_n^{2k+n})+w_n^{k+\frac{n}{2}}(w_n^{2k+n})=h_0(w_n^{2k})-w_n^{k}h_1(w_n^{2k})$

也就是知道$h_1(w_n^{2k})和h_0(w_n^{2k}),$就可以知道$h(w_n^{k})$和$h(w_n^{k+\frac{n}{2}})$

例如$h(w_4^0),h(w_4^1),h(w_4^2),h(w_4^3)$

$h(w_4^0)=h_0(w_4^0)+w_4^0h_1(w_4^0)$

$h_0(w_4^0)=h_{00}(w_4^0)+w_4^0h_{01}(w_4^0)$

$h(w_4^3)=h_0(w_4^0)-w_4^0h_1(w_4^0)$

$h_0(w_4^3)=h_{00}(w_4^3)-w_4^0h_{01}(w_4^3)$

$h_{00}(w_4^0)=a_0,h_{01}(w_4^0)=a1$

每次将原来的问题分成一半来处理递归层数$\log n$
就可以通过递归解决

IDFT

将点值表达式转化为多项式表达。

$f(x)\rightarrow {y_0,y_1,y_2,y_{n-1}}$
$B(x)=y_0x^0+y_1x^1+y_2x^2…y_{n-1}x^{n-1}$

设$B(w_n^{-k})=\sum y_i (w_n^{-k})^i=\sum \sum (a_j (w_n^{i})^j) (w_n^{-k})^i=\sum a_j\sum ( w_n^{j}w_n^{-k})^i$

$\sum (w_n^{j-k})^i=(j==k)?n:0$等比数列求和即可

$\rightarrow B(w_n^{-k})/n= a_k$

也就是带入$w_n^{-i}$当点值即可。

线代

$\left[ \begin{matrix} x_0^0 & x_0^2 &...& x_0^{n-1} \\ x_1^0 & x_1^2 &...& x_1^{n-1} \\ x_2^0 & x_2^2 &...& x_2^{n-1} \\ ... & .. &...& ... \\ x_{n-1}^0 & x_{n-1}^2 &...& x_{n-1}^{n-1} \\ \end{matrix} \right] \left[ \begin{matrix} a_0 \\ a_1 \\ a_2 \\ ... \\ a_{n-1} \\ \end{matrix} \right] =\left[ \begin{matrix} f_0 \\ f_1 \\ f_2 \\ ... \\ f_{n-1} \\ \end{matrix} \right]$

求左边矩阵的逆

$\left[ \begin{matrix} \frac{1}{n}(w_n^0)^0 &\frac{1}{n}(w_n^0)^1 &...& \frac{1}{n}(w_n^0)^{n-1} \\ \frac{1}{n}(w_n^{-1})^0 &\frac{1}{n}(w_n^{-1})^1 &...& \frac{1}{n}(w_n^{-1})^{n-1} \\ \frac{1}{n}(w_n^{-2})^0 &\frac{1}{n}(w_n^{-2})^1 &...& \frac{1}{n}(w_n^{-2})^{n-1} \\ ... & .. &...& ... \\ \frac{1}{n}(w_n^{-n+1})^0 &\frac{1}{n}(w_n^{-n+1})^1 &...& \frac{1}{n}(w_n^{-n+1})^{n-1} \\ \end{matrix} \right]$

为什么是逆矩阵，可以乘起来发现形式类似$\sum (w_n^{j-k})^i$

代码实现

$f(x)\rightarrow DFT$,
$g(x)\rightarrow DFT$,
$h(x)=f(x)\times g(x)$,
$h(x)\rightarrow IDFT$

蝴蝶变换

递归常数过大，考虑直接从底层向上推。那么就需要确定$a_i$最后会处于啥位置。可以推导，可以打表找规律，即二进制反过来。

保证扩大$n$，保证$n=2^k$
可以提前预处理$rev[abcde]=re[0abcd]>>1|[e0000]$

代码见板子。

NTT

原根

若 $gcd(a,m)=1$ ，使$a^l\equiv 1(mod \ m)$ 成立的最小的$l$ ，称为 $a$ 关于模$m$ 的阶。

根据欧拉定理$a^{\phi (m)}\equiv 1(mod \ m)$
若$g$ 关于模$m$ 的阶为$\phi(m)$,称 $g$ 为 $m$ 的一个原根

🐦可以证明原根符合单位根$w_n^i$的性质。

于是用$g^{\frac{p-1}{n}} \mod p$代替单位根。

证明🐦

但实际上由于快速傅里叶变换（$FFT$）实现的多项式乘法的过程中要求序列长度是 $2$ 的幂次，因此这里模数$p$ 还需要保证$p-1$ 的标准分解式中素因子$2$ 的幂次足够大。

代码见板子。

FWT

$FWT$ 和 $FFT$ 的核心思想应该是相同的，都是对数组的变换。我们记对数组 $A$ 进行快速沃尔什变换后得到的结果为$FWT(A)$

保证$n=2^k$

$or$

$FWT(A)=\sum_i\sum_{j|i=i} A(j)$

通过异的的性质

$A_0$或$A_1$得不到本身。
$A_1$或对应的$A_0$可以得到本身。

$FWT(A)=merge(FWT(A_0),FWT(A_0)+FWT(A_1))$

反向推导 $(a,b+a) \rightarrow (a,b)$

$UFWT(A)=merge(UFWT(A_0),UFWT(A_1)-UFWT(A_0))$

$and$

$FWT(A)=\sum_i\sum_{j\&i=i} A(j)$

通过与的性质

$A_0$与$A_1$得不到本身。
$A_1$只有自己才能得到右半边。
$A_1$或对应的$A_0$可以得左边。

$FWT(A)=merge(FWT(A_0)+FWT(A_1),FWT(A_0))$

反向推导 $(a+b,b) \rightarrow (a,b)$

$UFWT(A)=merge(FWT(A_0)-FWT(A_1),FWT(A_0))$

$xor$

$FWT(A)=\sum_i(\sum_{j|i=偶数} A(j)-\sum_{j|i=奇数} A(j))$

$FWT(A)=merge(FWT(A_1)-FWT(A_0),FWT(A_0)+FWT(A_1))$

反向推导 $(a+b,a-b) \rightarrow (a,b)$

$UFWT(A)=merge(\frac{FWT(A_1)-FWT(A_0)}{2},\frac{FWT(A_1)+FWT(A_0)}{2})$

代码见板子。