本系列恢復更新了，它將重新闡釋之前學過的演算法，
Fast Fourier Transform
快速傅里葉變換在演算法競賽中特指一種\(O(n\log n)\)轉換系數表示法和點值表示法的演算法，
單位根
記\(\omega_n\)為\(n\)次單位根，即\(\omega_n^n=1\)，
單位根有一個良好性質\(\omega_n^{k+\frac n2}=-\omega_n^k\)，可以通過復數的幾何意義來證明，
離散傅里葉變換
令\(A(x)=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}\)，
設\((b_0,b_1,b_2,\cdots,b_{n-1})\)是多項式\(A(x)\)的離散傅里葉變換，即將\((\omega_n^0,\omega_n^1,\omega_n^2,\cdots,\omega_n^{n-1})\)代入\(A(x)\)得到的點值表示，
再令\(B(x)=b_0+b_1x+b_2x^2+\cdots+b_{n-1}x^{n-1}\)，將\((\omega_n^0,\omega_n^{-1},\omega_n^{-2},\cdots,\omega_n^{-(n-1)})\)代入：
當\(j=k\)時，\(\omega_n^{j-k}=1\)；
當\(j\neq k\)時，\(\displaystyle\sum_{i=0}^{n-1}(\omega_n^{j-k})^i=\frac{(\omega_n^{j-k})^n-1}{\omega_n^{j-k}-1}=0\)，
故\(B(\omega_n^k)=na_k\)，將每一項除以\(n\)就可以得到\(A(x)\)，該程序即為離散傅里葉逆變換，
離散傅里葉變換最常用于多項式乘法中，由于兩個點值表示的多項式相乘是\(O(n)\)的，那么我們只需要對兩個多項式都進行離散傅里葉變換后相乘，再逆變換回來，就可以得到相乘后的系數表示的多項式，
這啟發我們用更優秀的復雜度進行傅里葉變換的程序，
分治
可以嘗試使用分而治之的方法，
將\(A(x)\)按下標奇偶分成兩部分，即令\(A_1(x)=a_0+a_2x+a_4x^2+\cdots+a_n-2x^{n-2}\)
蝴蝶操作
名字起的很美，
MTT
Blue-Steins
Number Theory Transform
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138425.html
標籤：其他