推薦博客 ： https://oi.men.ci/fft-notes/
卷積的理解 ： https://www.zhihu.com/question/22298352?rf=21686447
?
題目鏈接 ：http://uoj.ac/problem/34
?
這是一道模板題。
給你兩個多項式，請輸出乘起來后的多項式。
輸入格式
第一行兩個整數 nn 和 mm，分別表示兩個多項式的次數。
第二行 n+1n+1 個整數，表示第一個多項式的 00 到 nn 次項系數。
第三行 m+1m+1 個整數，表示第二個多項式的 00 到 mm 次項系數。
輸出格式
一行 n+m+1n+m+1 個整數，表示乘起來后的多項式的 00 到 n+mn+m 次項系數。
樣例一
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，保證輸入中的系數大于等于 0 且小于等于 9。
時間限制：1s1s
空間限制：256MB
?
題意? ： 給你兩個多項式的系數，從 0 到 n 給出，求這兩個多項式相乘后的系數，從小到大輸出
思路分析 ： 裸的 FFT ，參考kuangbin 的板子
就是要注意以下數組的大小，main中的 len 是 2^k ， 因此當m+n = 2e5 左右時，此時 2^k = 260000+ ， 因此要注意數組的大小
代碼示例：
#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表示二進制位數,計算一個數在二進制翻轉之后形成的新數
{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表示我的多項式位數
{for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);//中間的那個if保證了每個數做多只被交換了1次//如果不寫那么會有一些數被交換兩次,導致最終的位置沒有變for(int step=1;step<n;step<<=1)//模擬一個合并的過程{cd wn=exp(cd(0,dft*PI/step));//計算當前單位復根for(int j=0;j<n;j+=step<<1){cd wnk(1,0);//計算當前單位復根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)的體現a[k+step]=x-y;//后半個“step”中的ω一定和“前半個”中的成相反數//“紅圈”上的點轉一整圈“轉回來”，轉半圈正好轉成相反數//一個數相反數的平方與這個數自身的平方相等..wnk*=wn;}}}if(dft==-1) for(int i=0;i<n;i++) a[i]/=n;//考慮到如果是IDFT操作,整個矩陣中的內容還要乘上1/n
}
?
)
