如何做中英文切换的双语网站,ps做的网站如何转入dw,唐山网站制作企业,城市分站seoFFT是什么#xff1f; FFT是快速傅里叶变换(fast Fourier transform)的简称。在ACM领域主要是用来快速求解多项式乘法的算法#xff0c; 在信号领域也有很大用途 基础知识 卷积 举个例子#xff0c;给你两个向量 \(a (a_0, a_1, a_2), b(b_0, b_1, b_2)\) a和b的卷积就是$ (…FFT是什么 FFT是快速傅里叶变换(fast Fourier transform)的简称。在ACM领域主要是用来快速求解多项式乘法的算法 在信号领域也有很大用途 基础知识 卷积 举个例子给你两个向量 \(a (a_0, a_1, a_2), b(b_0, b_1, b_2)\) a和b的卷积就是$ ( a_0b_0, a_1b_0a_0b_1, a_2b_0a_1b_1a_0b_2, a_1b_2a_2b_1, a_2b_2 ) $ 即可以看作两个多项式\(A(x)a_0a_1x^1a_2x^2和B(x)b_0b_1xb_2x^2\)相乘。 所以卷积就可看做多项式乘法。那些形如\(c_k \Sigma_{i0}^{k}a_ib_{k-i}\)卷积的就可以类比成多项式乘法 就可通过fft快速求解。多项式 多项式有两种表达形式一种是系数表达形如\(A(x) \Sigma_{i0}^{n-1} a_ix^i\)另一种是点值表达 形如\((x_1, y_1), (x_2, y_2), (x_3, y_3)...(x_m, y_m)\), 且mn多项式的点值表示和插值表示可以互推\(w_ne^{2\pi i/n}\) \(w_n^{n/2k}-w_n^k\)\(w_n^{2k}w_{n/2}^k\)$ \Sigma_{j0}^{n-1}w_n^{jk} (k%n0)?n:0$傅里叶变换的原理 在傅里叶变换里面系数表达和点值表达如何互推 一个暴力点的方法系数表达-点值表达 \(y_k \Sigma_{i0}^{n-1}a_iw_n^{ki}\) 点值表达-系数表达 \(a_k 1/n*\Sigma_{i0}^{n-1}y_iw_n^{-ki}\) 证明看黑板所以不论是系数表达推点值表达还是点值表达推系数表达方法都一样 如何快速的求出上面的式子呢 假设 $A(x)a_0a_1xa_2x^2...a_{n-1}x^{n-1} $ 那\(A(x)(a_0a_2x^2a_4x^4...a_{n-2}x^{n-2})(a_1xa_3x^3..a_{n-1}x^{n-1})\) 令\(A_0(x)a_0a_2xa_4x^2...a_{n-2}x^{n/2-1}, A_1(x)a_1a_3xa_5x...a_{n-1}x^{n/2-1}\) 则\(A(x) A_0(x^2)xA_1(x^2)\) 那么就可以用\(A_0(w_{n/2}^0), A_0(w_{n/2}^1) ... A_0(w_{n/2}^{n/2-1})\) 和 \(A_1(w_{n/2}^0), A_1(w_{n/2}^1) ... A_1(w_{n/2}^{n/2-1}\) 得出\(A(w_{n}^0), A(w_{n}^1) ... A(w_{n}^{n-1})\) \(所以可以采用递归分治的办法求解FFT\) 分治图 void ntt(ll* a, int n, int t) {rep(i, 0, n) {int rv rev(i,n);if(irv) swap(a[i], a[rv]);}ll g1;if(t1) g3;else ginv[3];for(int m2; mn1; m1) {ll wm mypow(g, (MOD-1)/m);int midm1;for(ll *pa; pan; pm) {ll w1;rep(i, 0, mid) {ll tw*(p[midi]);p[midi] p[i]-t;p[i] p[i]t;w w*wm%MOD;p[i]%MOD, p[midi]%MOD;}}}if(t-1) {rep(i, 0, tn)a[i]a[i]*inv[n]%MOD;}
}
void fft(ll *a, ll* b, int n) {int tnMAXN;while(tn/4n) tn1;ntt(a, tn, 1);ntt(b, tn, 1);rep(i, 0, tn)a[i] a[i]*b[i]%MOD;ntt(a, tn, -1);
}NTT \(w_ng^{(P-1)/n}\%P\) 一些更高级的操作或例题https://wenku.baidu.com/view/20c234cf581b6bd97f19eaea.htmlhttp://blog.csdn.net/samjia2000/article/details/65661468https://www.cnblogs.com/candy99/p/6738010.html转载于:https://www.cnblogs.com/Merodach/p/7395604.html
