还在学简单的fft,ac没想过但是wa倒是没想到,而且全错,下载数据点发现输出都一样(?)这是为什么呢
#include<iostream>
#include<cstdio>
#include<cstdio>
#include<cmath>
#define Maxn 13500000
using namespace std;
long long n,m;
long long limit = 1;
const double Pi = acos(-1.0);
struct cp {
double x,y;
cp (double xx = 0,double yy = 0) {
x = xx;
y = yy;
}
}a[Maxn],b[Maxn];
cp operator + (cp a,cp b) {
return cp(a.x + b.x,a.y + b.y);
}
cp operator - (cp a,cp b) {
return cp(a.x - b.x,a.y - b.y);
}
cp operator * (cp a,cp b) {
return cp(a.x*b.x - a.y*b.y,a.x*b.y + a.y*b.x);
}
void fft(long long limit,cp *a,long long type) {
if(limit == 1)
return;
cp a1[limit>>1],b1[limit>>1];
for(long long i = 0;i <= limit;i+=2)
a1[i >> 1] = a[i],b1[i >> 1] = a[i+1];
fft(limit>>1,a1,type);
fft(limit>>1,b1,type);
cp Wn = cp(cos(2.0*Pi/limit),type * sin(2.0*Pi/limit)),w = cp(1,0);
for(long long i = 0;i < (limit>>1);i++,w = w*Wn) {
cp t = w * b1[i];
a[i] = a1[i] + t;
a[i+(limit>>1)] = a1[i] - t;
}
}
int main() {
cin >> n >> m;
for(long long i = 0;i <= n;i++) cin >> a[i].x;
for(long long j = 0;j <= m;j++) cin >> b[j].x;
while(limit <= n+m)
limit <<= 1;
fft(limit,a,1);
fft(limit,b,1);
for(long long i = 0;i <= limit;i++)
a[i] = a[i] * b[i];
fft(limit,a,-1);
for(long long i = 0;i <= n+m;i++) {
printf("%d ",(long long)(a[i].x/limit + 0.49));
}
return 0;
}