洛谷P3803 【模板】多项式乘法（FFT）

Code: 

复制代码#include<bits/stdc++.h> #define maxn 5000001 #define setIO(s) freopen(s".in","r",stdin) using namespace std; const double pi=acos(-1.0); struct cpx { double x,y; cpx(double a=0,double b=0) {x=a, y=b; } cpx operator+(const cpx b) { return cpx(x+b.x,y+b.y); } cpx operator-(const cpx b) { return cpx(x-b.x,y-b.y); } cpx operator*(const cpx b) { return cpx(x*b.x-y*b.y,x*b.y+y*b.x); } }A[maxn],B[maxn]; void FFT(cpx *a,int n,int flag) { for(int i=0,k=0;i<n;++i) { if(i>k) swap(a[i], a[k]); for(int j=n>>1;(k^=j)<j;j>>=1); } for(int mid=1;mid<n;mid<<=1) { cpx wn(cos(pi/mid), flag*sin(pi/mid)),x,y; for(int j=0;j<n;j+=(mid<<1)) { cpx w(1,0); for(int k=0;k<mid;++k) { x=a[j+k], y=w*a[j+k+mid]; a[j+k]=x+y,a[j+k+mid]=x-y; w=w*wn; } } } if(flag==-1) for(int i=0;i<n;++i) a[i].x/=(double)n; } int main() { // setIO("input"); int n,m,len=1; 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); for(len=1;len<(n+m+1);len<<=1); FFT(A, len, 1), FFT(B, len, 1); for(int i=0;i<len;++i) A[i]=A[i]*B[i]; FFT(A, len, -1); for(int i=0;i<=n+m;++i) printf("%d ",(int)(A[i].x+0.5)); return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#define maxn 5000001
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const double pi=acos(-1.0);
struct cpx
{
double x,y;
cpx(double a=0,double b=0) {x=a, y=b; }
cpx operator+(const cpx b) { return cpx(x+b.x,y+b.y); }
cpx operator-(const cpx b) { return cpx(x-b.x,y-b.y); }
cpx operator*(const cpx b) { return cpx(x*b.x-y*b.y,x*b.y+y*b.x); }
}A[maxn],B[maxn];
void FFT(cpx *a,int n,int flag)
{
for(int i=0,k=0;i<n;++i)
{
if(i>k) swap(a[i], a[k]);
for(int j=n>>1;(k^=j)<j;j>>=1);
}
for(int mid=1;mid<n;mid<<=1)
{
cpx wn(cos(pi/mid), flag*sin(pi/mid)),x,y;
for(int j=0;j<n;j+=(mid<<1))
{
cpx w(1,0);
for(int k=0;k<mid;++k)
{
x=a[j+k], y=w*a[j+k+mid];
a[j+k]=x+y,a[j+k+mid]=x-y;
w=w*wn;
}
}
}
if(flag==-1)
for(int i=0;i<n;++i) a[i].x/=(double)n;
}
int main()
{
// setIO("input");
int n,m,len=1;
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);
for(len=1;len<(n+m+1);len<<=1);
FFT(A, len, 1), FFT(B, len, 1);
for(int i=0;i<len;++i) A[i]=A[i]*B[i];
FFT(A, len, -1);
for(int i=0;i<=n+m;++i) printf("%d ",(int)(A[i].x+0.5));
return 0;
}