dWoi Round 2 D 题解
一只书虫仔
·
·
题解
from DreamWasTaken。
\text{DFT}(b)_i=\sum_{j=0}^{2^n-1}b_j\omega^{ij}\mod{998244353}
$$\text{DFT}^2(b)_i=\sum_{j=0}^{2^n-1}\left(\sum_{k=0}^{2^n-1}b_k\omega^{jk}\right)\omega^{ij}=\sum_{k=0}^{2^n-1}b_k\sum_{j=0}^{2^n-1}\omega^{j(k+i)}$$
由单位根反演，有：
$$\text{DFT}^2(b)_i=\sum_{k=0}^{2^n-1}b_k2^n[k+i\in\{0,2^n\}]$$
$$\text{DFT}^2(b)_i=2^nb_{2^n-i\mod2^n}$$
再迭代一次得到：
$$\text{DFT}^4(b)_i=4^nb_i$$
对每一项乘 $4^{\lfloor \frac k 4\rfloor}$，再进行 $k\bmod 4$ 次 DFT 即可。