单位根
\[\large\begin{aligned}
&\omega_n^k=e^{\frac{2\pi ik}{n}}=\cos\frac{2πk}{n}+i\sin\frac{2πk}{n} \\
&\omega_{n}^{n}=1 \\
&\omega_{2n}^{2k}=\omega_n^k \\
&\omega_{n}^{k+\frac{n}{2}}=-\omega_n^k \\
&\sum_{i=1}^{n-1} \omega_n^i = 0
\end{aligned}
\]
单位根反演
\[\large [n\mid k]=\frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ik}
\]
若 \(n\mid k\) 时，得
\[\large \frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ik}=\frac{1}{n}\sum_{i=0}^{n-1}\omega_n^n=1
\]
若 \(n\nmid k\) 时，得
\[\large \frac{1}{n}\sum_{i=0}^{n-1}\omega_{n}^{ik}=\frac{1}{n}\omega_n^{0}\frac{1-\omega_n^{nk}}{1-\omega_n^{k}}=0
\]
可以用来求多项式某个倍数的系数和：
\[\large\begin{aligned}
&\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} [x^{ik}] f(x) \\
=&\sum_{i=0}^n [x^{i}] f(x)[k \mid i] \\
=&\sum_{i=0}^n [x^{i}] f(x)\frac{1}{k}\sum_{j=0}^{k-1}\omega_k^{ij} \\
=&\frac{1}{k} \sum_{j=0}^{k-1} \sum_{i=0}^n [x^{i}] f(x)(\omega_k^j)^i \\
=&\frac{1}{k} \sum_{j=0}^{k-1} f(\omega_k^j) \\
\end{aligned}
\]
证明 \(IDFT\) 正确性：
\[\large\begin{aligned}
\ [x^k] \widehat{f}(x) &= \sum_{i=0}^{n-1} \omega_n^{-ik}f(\omega_n^i) \\
&= \sum_{i=0}^{n-1} \omega_n^{-ik}\sum_{j=0}^{n-1} \omega_n^{ij} [x^j] f(x)\\
&= \sum_{j=0}^{n-1} [x^j] f(x) \sum_{i=0}^{n-1} \omega_n^{i(j-k)} \\
&= n\sum_{j=0}^{n-1} [x^j] f(x) [n\mid (j-k)] \\
&= n[x^k] f(x) \\
\ [x^k] \widehat{f}(x) &= \sum_{i=0}^{n-1} \omega_n^{ik}f(\omega_n^i) \\
&= \sum_{i=0}^{n-1} \omega_n^{ik}\sum_{j=0}^{n-1} \omega_n^{ij} [x^j] f(x)\\
&= \sum_{j=0}^{n-1} [x^j] f(x) \sum_{i=0}^{n-1} \omega_n^{i(j+k)} \\
&= [x^0] f(x) \sum_{i=0}^{n-1} \omega_n^{ik} +\sum_{j=1}^{n-1} [x^{n-j}] f(x) \sum_{i=0}^{n-1} \omega_n^{i(k-j)} \\
&= n [x^0] f(x)[n \mid k] + n \sum_{j=1}^{n-1} [x^{n-j}] f(x) [n \mid (k-j)] \\
\end{aligned}
\]