首先根據(jù)單位根反演，問題可以轉(zhuǎn)化為對于一個(gè)多項(xiàng)式帶入\(N\)個(gè)單位根求值。
形式化地說：給定\(F(x)=F[0]+F[1]x+F[2]x^2+\cdots +F[N-1]x^{N-1}\),對\(k\in [0,N-1]\)求出\(G[k]=F(\omega_N^k)\)
考慮分治，\(F(x)\)的系數(shù)分成奇偶兩部分，分別設(shè)：
\(FL(x)=F[0]+F[2]x+\cdots +F[N-2]x^{\frac{N}{2}-1}\)
\(FR(x)=F[1]+F[3]x+\cdots +F[N-1]x^{\frac{N}{2}-1}\)
則不難發(fā)現(xiàn)\(F(x)=FL(x^2)+xFR(x^2)\)
我們把單位根帶入進(jìn)去，即
\(F(\omega_N^k)=FL(\omega_N^{2k})+\omega_N^kFR(\omega_N^{2k})\)
接下來分兩種情況，令\(k\in [0,\frac{N}{2}-1]\)
那么
\(F(\omega_N^k)=FL(\omega_{\frac{N}{2}}^{k})+\omega_N^kFR(\omega_{\frac{N}{2}}^{k})\)
\(F(\omega_N^{\frac{N}{2}+k})=FL(\omega_{\frac{N}{2}}^{k})-\omega_N^kFR(\omega_{\frac{N}{2}}^{k})\)
以上是單位根的推法，但是平常更多是使用模意義下的原根，因此我們先要找到\(\omega_N^1\)在原根中對應(yīng)的東西。
我們假設(shè)模數(shù)為質(zhì)數(shù)\(p\)，原根為\(g\)，則\(g^k(k\in [0,p-2])\)恰好取遍膜\(p\)意義下的所有數(shù)
假設(shè)\(\omega_N^1\)對應(yīng)于\(g^k\)，那么\(g^k\)的階為\(N\),即\(\frac{p-1}{gcd(p-1,k)}=N\),因此要求\(N|p-1\)。
那么取\(k=\frac{p-1}{N}\)即可滿足要求。同時(shí)我們可以代入上面的式子，可以發(fā)現(xiàn)之前的性質(zhì)依然成立。
實(shí)現(xiàn)時(shí)，通常采用蝴蝶變換的技巧，把遞歸變成遞推。
例如第\(6(110_2)\)個(gè)位置的系數(shù),落到底層即為第\(3(011_2)\)個(gè)位置（當(dāng)\(N=2^3\)時(shí)）
實(shí)際上就是將這個(gè)數(shù)的二進(jìn)制反轉(zhuǎn)
證明考慮如果當(dāng)前是奇數(shù)就會(huì)落到右邊，偶數(shù)就會(huì)落到左邊。