https://www.luogu.com.cn/problem/P3803
题意：给出两个多项式，求两个多项式的卷积。
1解法：FFT递归版，因为递归每次传数组导致慢。
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF 0x3f3f3f3f
#define mod 20191117
#define PI acos(-1)
using namespace std;
typedef long long ll ;
const int MAXN = 2*1e6+10;
const double pi =acos(-1.0);
struct complex{
double x , y ;
complex(double xx = 0 , double yy = 0){
x = xx , y = yy ;
}
}a[MAXN],b[MAXN];
complex operator + (complex a , complex b)
{
return complex(a.x+b.x , a.y+b.y);
}
complex operator - (complex a , complex b)
{
return complex(a.x-b.x , a.y-b.y);
}
complex operator * (complex a , complex b)
{
return complex(a.x*b.x - a.y*b.y , a.x*b.y+a.y*b.x);
}
void fast_fast_tle(int limit , complex *a , int type)
{
if(limit == 1) return ;//只有一个常数项
complex a1[limit>>1] , a2[limit>>1];
for(int i = 0 ; i <= limit ; i+=2)
a1[i>>1] = a[i] , a2[i>>1] = a[i+1];//下标分奇偶存入两数组
fast_fast_tle(limit>>1 , a1 , type);//分治
fast_fast_tle(limit>>1 , a2 , type);
complex Wn = complex(cos(2.0*pi/limit) , type*sin(2.0*pi/limit)), w = complex(1 , 0);//单位根及幂
for(int i = 0 ; i < (limit>>1) ; i++ , w = w * Wn)
{
a[i] = a1[i] + w*a2[i];
a[i+(limit>>1)] = a1[i] - w*a2[i];//利用单位根的性质，得到另一部分
}
}
int main()
{
int n , m;
scanf("%d%d" , &n , &m);
for(int i = 0 ; i <= n ; i++) scanf("%lf" , &a[i].x);
for(int i = 0 ; i <= m ; i++) scanf("%lf" , &b[i].x);
int limit = 1 ; while(limit <= n+m) limit <<= 1;
fast_fast_tle(limit , a , 1);
fast_fast_tle(limit , b , 1);
//1表示从系数表示法变为点值表示
for(int i = 0 ; i <= limit ; i++)
a[i] = a[i] * b[i];//点值表示法的乘积O（n）
fast_fast_tle(limit , a , -1);
//傅里叶逆变换，-1表示点值表示法变为系数表示法
for(int i = 0 ; i <= n+m ; i++) cout << (int)(a[i].x/limit+0.5) << " ";
return 0;
}
2解法：FFT迭代版，因为我们需要求的序列实际是原序列下标的二进制反转！
这样我们可以O(n)的利用某种操作得到我们要求的序列，然后不断向上合并就好了.
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF 0x3f3f3f3f
#define mod 20191117
#define PI acos(-1)
using namespace std;
typedef long long ll ;
const int MAXN = 3e6+9;
const double pi =acos(-1.0);
int r[MAXN] , limit = 1 , l = 0;
struct complex{
double x , y ;
complex(double xx = 0 , double yy = 0){
x = xx , y = yy ;
}
}a[MAXN],b[MAXN];
complex operator + (complex a , complex b)
{
return complex(a.x+b.x , a.y+b.y);
}
complex operator - (complex a , complex b)
{
return complex(a.x-b.x , a.y-b.y);
}
complex operator * (complex a , complex b)
{
return complex(a.x*b.x - a.y*b.y , a.x*b.y+a.y*b.x);
}
void fast_fast_tle(complex *a , int type)
{
for(int i = 0 ; i < limit ; i++)
if(i < r[i]) swap(a[i] , a[r[i]]);//将序列下标变成迭代序列
for(int mid = 1 ; mid < limit ; mid<<=1)//待合并的中点
{
complex Wn(cos(pi/mid) , type*sin(pi/mid));//单位根
for(int R = mid<<1 , j = 0 ; j < limit ; j+=R)//R是区间右端点，j表示目前位置
{
complex w(1,0);
for(int k = 0 ; k < mid ; k++ , w = w * Wn)//枚举左半部分
{
complex x = a[j+k] , y = w * a[j+mid+k];//蝴蝶效应
a[j+k] = x + y ;
a[j+mid+k] = x - y ;
}
}
}
}
int main()
{
int n , m ;
scanf("%d%d" , &n , &m);
for(int i = 0 ; i <= n ; i++) scanf("%lf" , &a[i].x);
for(int i = 0 ; i <= m ; i++) scanf("%lf" , &b[i].x);
while(limit <= n+m) limit <<= 1 , l++;
for(int i = 0 ; i < limit ; i++)
{
r[i] = (r[i>>1]>>1) | ((i&1) << (l-1));//将标号二进制数反过来，存入r[i]数组中
}
fast_fast_tle(a , 1);
fast_fast_tle(b , 1);
for(int i = 0 ; i <= limit ; i++) a[i] = a[i]*b[i];
fast_fast_tle(a , -1);
for(int i = 0 ; i <= n+m ; i++)
printf("%d " , (int)(a[i].x/limit + 0.5));
return 0;
}