qbxt 数学 day7
_HwH_
·
·
个人记录
多项式
复数
定义
-
i=\sqrt-1
-
z=a + bi$ ，可以对应复平面上的一个点 $(a,b)
单位复数根
-
$$
\omega_n = \cos\frac{2\pi}{n} + \sin\frac{2\pi}{n} * i
\\
\omega_n^k = \cos\frac{2\pi k}{n} + \sin{\frac{2\pi k}{n}} *i
$$
性质
-
\omega_n^k = \omega_{2n}^{2k}
-
\omega_n^{k + \frac{n}{2}} = - \omega_n^k
-
\omega_n^0 = \omega_n^n =1
点值表示法 (DFT)
多项式原始表示法：f(x) = \sum_{i=0}^{n}{a_i x^i}
点值表示法：\{ (x_1 , f(x_1)) , (x_2 , f(x_2)) ,..., (x_n , f(x_n)) \}
点值表示法表示多项式乘法： \{ (x_1 , g(x_1)f(x_1)) , ... , (x_n , g(x_n)f(x_n)) \}
快速傅里叶变换 (FFT)
首先，假设 n = 2^k ， 多项式 A(x) = \sum_{i=0}^{n-1}{a_i x^i} ，使用点值表示法，将 \omega_n^0 , \omega_n^1 ... \omega_n^{n-1} 代入
令：
A_1 (x) = a_0 +a_2 x + a_4 x^2 +...+ a_{n-2} x^{\frac{n}{2}-1}
\\
A_2 (x) = a_1 +a_3 x + a_5 x^2 +...+ a_{n-1} x^{\frac{n}{2}-1}
则 A(x)= A_1 (x^2) + x A_2 (x^2)
所以
A(\omega_n^k) = A_1 (w_n^{2k}) + \omega_n^k A_2(w_n^{2k}) = A_1(\omega_{\frac{n}{2}}^k) + \omega_n^k A_2(\omega_{\frac{n}{2}}^{k})
同理
A(\omega_n^{k+ \frac{n}{2}}) = A_1 (\omega_{\frac{n}{2}}^k) - \omega_n^k A_2(\omega_{\frac{n}{2}}^k)
于是可以递归求解，共 \log(n) 层
快速傅里叶逆变换 (IDFT)
令 y = DFN(f) ， c_k =\sum_{i=0}^{n-1}{y_i (\omega_n^{-k})^i}
则:
c_k = \sum_{i=0}^{n-1}{y_i (\omega_n^{-k})^i} =\sum_{i=0}^{n-1} \sum_{j=0}^{n-1}{a_j (\omega_n^i)(\omega_n^{-k})^i} = \sum_{j=0}^{n-1}{a_j} \sum_{i=0}^{n-1}{(\omega_n^{j-k})^i}
令 S(x) = \sum_{i=0}^{n-1}{x^i}
当 k \neq 0 时， S(\omega_n^k) = 1 + (\omega_n^k) +(\omega_n^k)^2 +...
就有：\omega_n^k S(\omega_n^k) = \omega_n^k + (\omega_n^k)^2 +(\omega_n^k)^3 +...
所以
S(\omega_n^k) = \frac{(\omega_n^k)^n -1}{\omega_n^k -1} = 0
当 k=0 时， S(\omega_n^k) = n
所以 c_k= \sum_{j=0}^{n-1}{a_j} \sum_{i=0}^{n-1}{(\omega_n^{j-k})^i} 就有： c_k = a_k n
只需反着做一遍 FFT
数论变换 (NTT)
在模意义下的多项式乘法，通过类似 (FFT) 的操作将复杂度降至 O( n \log n)
设 g 为模质数 p 的原根
则 p-1 = q \times 2^r = q \times n
设 \omega_n = g^q ， 则 \omega_n , \omega_n^2 , .... , \omega_n^n 两两不同
且 \omega_n^n = g^{nq} = g^{p-1} = 1
可证明， \omega_n^k = \omega_{2n}^{2k} , \omega_n^{k+\frac{n}{2}} = -\omega_n^k 成立
可证明： k \neq 0 时， \sum_{i=0}^{n-1}{(w_n^k)^i} = 0 ；且 k = 0 时， \sum_{i=0}^{n-1}{(w_n^k)^i} = n
在实践中，常用 998244353 = 119 \times 2^{23} + 1
快速沃尔什变换 (FWT)
原来的多项式乘法：C_{i+j} = \sum_i \sum_j {A_i \times B_j}
新的多项式乘法： C_{i \bigotimes j} = \sum_i \sum_j {A_i \times B_j}
目标： C = A * B ，则希望求 FWT(C) = FTW(A) * FWT(B) ，之后再进行逆变换
当该运算为 or 运算
FWT(A) = \left\{
\begin{aligned}
(FWT(A_0),FWT(A_0) + FWT(A_1)) , n > 1\\
A, n=1
\end{aligned}
\right.
其中 A_0 为前半段， A_1 为后半段，上式可用数学归纳法证明
当该运算为与运算
FWT(A) = \left\{
\begin{aligned}
(FWT(A_0)+FWT(A_1) , FWT(A_1)) , n > 1\\
A, n=1
\end{aligned}
\right.
当该运算为异或时
FWT(A) = \left\{
\begin{aligned}
(FWT(A_0)+FWT(A_1) , FWT(A_0)-FWT(A_1)) , n > 1\\
(FWT(A_0)-FWT(A_1) , FWT(A_0)+FWT(A_1)) , n > 1\\
A, n=1
\end{aligned}
\right.
最后进行 IFWT 即可