推薦博客 ： https://oi.men.ci/fft-notes/

卷積的理解 ： https://www.zhihu.com/question/22298352?rf=21686447

?

題目鏈接 ：http://uoj.ac/problem/34

?

這是一道模板題。

給你兩個(gè)多項(xiàng)式，請輸出乘起來后的多項(xiàng)式。
輸入格式

第一行兩個(gè)整數(shù) nn 和 mm，分別表示兩個(gè)多項(xiàng)式的次數(shù)。

第二行 n+1n+1 個(gè)整數(shù)，表示第一個(gè)多項(xiàng)式的 00 到 nn 次項(xiàng)系數(shù)。

第三行 m+1m+1 個(gè)整數(shù)，表示第二個(gè)多項(xiàng)式的 00 到 mm 次項(xiàng)系數(shù)。
輸出格式

一行 n+m+1n+m+1 個(gè)整數(shù)，表示乘起來后的多項(xiàng)式的 00 到 n+mn+m 次項(xiàng)系數(shù)。
樣例一
input

1 2
1 2
1 2 1

output

1 4 5 2

explanation

(1+2x)?(1+2x+x2)=1+4x+5x2+2x3(1+2x)?(1+2x+x2)=1+4x+5x2+2x3。
限制與約定

0≤n,m≤105，保證輸入中的系數(shù)大于等于 0 且小于等于 9。

時(shí)間限制：1s1s

空間限制：256MB

?

題意? ： 　給你兩個(gè)多項(xiàng)式的系數(shù)，從 0 到 n 給出，求這兩個(gè)多項(xiàng)式相乘后的系數(shù)，從小到大輸出

思路分析 ： 裸的 FFT ，參考kuangbin 的板子

　　　　就是要注意以下數(shù)組的大小，main中的 len 是 2^k ， 因此當(dāng)m+n = 2e5 左右時(shí)，此時(shí) 2^k = 260000+ ， 因此要注意數(shù)組的大小

代碼示例：

#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn = 2e5+63000; const double pi = acos(-1.0); int n, m; struct Complex{double x, y;Complex (double _x=0, double _y=0):x(_x), y(_y){}Complex operator -(const Complex &b)const{return Complex(x-b.x, y-b.y);}Complex operator +(const Complex &b)const{return Complex(x+b.x, y+b.y);}Complex operator *(const Complex &b)const{return Complex(x*b.x-y*b.y, x*b.y+y*b.x);} };Complex x1[maxn], x2[maxn]; int sum[maxn]; void change(Complex y[], int len){for(int i = 1, j = len/2; i < len-1; i++){if (i < j) swap(y[i], y[j]);int k = len/2;while(j >= k){j -= k;k /= 2;}if (j < k) j += k;} }void fft(Complex y[], int len, int on){change(y, len);for(int h = 2; h <= len; h <<= 1){Complex wn(cos(-on*2*pi/h), sin(-on*2*pi/h));for(int j = 0; j < len; j += h){Complex w(1, 0);for(int k = j; k < j+h/2; k++){Complex u = y[k];Complex t = w*y[k+h/2];y[k] = u+t;y[k+h/2] = u-t;w = w*wn;}}}if (on == -1){for(int i = 0; i < len; i++)y[i].x /= len;} }int main () {cin >> n >> m;int len = 1;while(len <= (n+m)) len <<= 1;for(int i = 0; i <= n; i++) scanf("%lf", &x1[i].x);fft(x1, len, 1);for(int i = 0; i <= m; i++) scanf("%lf", &x2[i].x);fft(x2, len, 1);for(int i = 0; i < len; i++)x1[i] = x1[i]*x2[i];fft(x1, len, -1);for(int i = 0; i <= n+m; i++){sum[i] = (int)(x1[i].x+0.5); // sum[] 是最后的答案 printf("%d%c", sum[i], i ==n+m?'\n':' ');}return 0; }

?

____________________________________________________________________________

int rev[maxl]; void get_rev(int bit)//bit表示二進(jìn)制位數(shù),計(jì)算一個(gè)數(shù)在二進(jìn)制翻轉(zhuǎn)之后形成的新數(shù) {for(int i=0;i<(1<<bit);i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1)); } void fft(cd *a,int n,int dft)//n表示我的多項(xiàng)式位數(shù) {for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);//中間的那個(gè)if保證了每個(gè)數(shù)做多只被交換了1次//如果不寫那么會(huì)有一些數(shù)被交換兩次,導(dǎo)致最終的位置沒有變for(int step=1;step<n;step<<=1)//模擬一個(gè)合并的過程{cd wn=exp(cd(0,dft*PI/step));//計(jì)算當(dāng)前單位復(fù)根for(int j=0;j<n;j+=step<<1){cd wnk(1,0);//計(jì)算當(dāng)前單位復(fù)根for(int k=j;k<j+step;k++){//蝴蝶操作cd x=a[k];cd y=wnk*a[k+step];a[k]=x+y;//這就是上文中F(x)=G(x)+ωH(x)的體現(xiàn)a[k+step]=x-y;//后半個(gè)“step”中的ω一定和“前半個(gè)”中的成相反數(shù)//“紅圈”上的點(diǎn)轉(zhuǎn)一整圈“轉(zhuǎn)回來”，轉(zhuǎn)半圈正好轉(zhuǎn)成相反數(shù)//一個(gè)數(shù)相反數(shù)的平方與這個(gè)數(shù)自身的平方相等..wnk*=wn;}}}if(dft==-1) for(int i=0;i<n;i++) a[i]/=n;//考慮到如果是IDFT操作,整個(gè)矩陣中的內(nèi)容還要乘上1/n }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ccut-ry/p/9498240.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的FFT 入门的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。