[学习笔记] - 基本数论：快速傅立叶变换
最编程
2024-03-01 11:17:49
...
点表示法求出系数表达式
FFT的逆变换怎么搞？
已有\(n\)个点\((\omega_n^{k},A(\omega_n^{k}))\)
我们为了方便将其称之为\((x_k,y_k)\)
\[C_k=\sum_{i=1}^{n-1}y_i(\omega_n^{-k})^i
\]
我们可以把这个当做一个关于\(y\)的多项式，\(B(x)=y_0+y_1x+\cdots+y_{n-1}x^{n-1}\)
\[C_k=B(\omega_{n}^{-k})
\]
我们可以再做一次傅里叶变换来求解系数表示式
但是\(C_k\)并不是原多项式的系数，需要再除以一个\(n\)
\[\begin{align}
C_k=\sum_{i=1}^{n-1}y_i(\omega_n^{-k})^i
&=\sum_{i=1}^{n-1}(\sum_{j=0}^{n-1}a_j{\omega_n^{i}}^j){\omega_n^{-k}}^i\\
&=\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}a_j(\omega_{n}^{j-k}))^i\\
&=\sum_{j=0}^{n-1}a_j(\sum_{i=0}^{n-1}(\omega_{n}^{j-k})^{i})
\end{align}\]
我们把\(\sum_{i=0}^{n-1}(\omega_{n}^{j-k})^{i}\)可以看做一个多项式
\(S(x)=1+x+x^2\cdots+x^{n-1}\)
这么这里就相当于\(S(\omega_{n}^{k})\)
分两种情况来看
-
\(①.\) \(k \ne 0\)
\[S(\omega_{n}^{k}) \gets \omega_{n}^{k}S(\omega_{n}^{k}) \]发现这两个式相等
所以\((1-\omega_{n}^{k})S(\omega_{n}^{k})=0\)
因为\(\omega_{n}^{k}\ne 1\)
所以\(S(\omega_{n}^{k})=0\)
-
\(②.\) \(k=0\)
\(S(\omega_{n}^k)=S(1)=n\)
因此
\[\sum_{j=0}^{n-1}a_j(\sum_{i=0}^{n-1}(\omega_{n}^{j-k})^{i})=na_k
\]