样例过了,求调
#include <bits/stdc++.h>
using namespace std;
struct Complex{
long double Real = 0;
long double Virtual = 0;
friend Complex operator+(Complex a, Complex b){
return {a.Real + b.Real, a.Virtual + b.Virtual};
}
friend Complex operator-(Complex a, Complex b){
return a + Complex{-b.Real, -b.Virtual};
}
friend Complex operator*(Complex a, Complex b){
return {a.Real * b.Real - a.Virtual * b.Virtual, a.Virtual * b.Real + a.Real * b.Virtual};
}
};
vector<Complex> FFT(vector<Complex>& ratios, int n, bool IDFT = false){
if(ratios.size() == 1) return vector<Complex>(n, ratios[0]);
vector<Complex> even, odd;
for(int i = 0; i < ratios.size(); i++){
if(i % 2 == 0) even.push_back(ratios[i]);
else odd.push_back(ratios[i]);
}
vector<Complex> ye = FFT(even, n / 2), yo = FFT(odd, n / 2), result;
result.resize(n);
int flag = (IDFT) ? -1 : 1;
Complex omega = {cos(2 * M_PI / (long double)n), flag * sin(2 * M_PI / (long double)n)};
result[0] = ye[0] + yo[0];
result[n / 2] = ye[0] - yo[0];
for(int i = 1; i < n / 2; i++, omega = omega * omega){
result[i] = ye[i] + omega * yo[i];
result[i + n / 2] = ye[i] - omega * yo[i];
}
return result;
}
vector<Complex> F, G;
int main(){
int n, m;
scanf("%d %d", &n, &m);
for(int i = 0, t; i <= n; i++){
scanf("%d", &t);
F.push_back(Complex{(long double)t, 0.0});
}
for(int i = 0, t; i <= m; i++){
scanf("%d", &t);
G.push_back(Complex{(long double)t, 0.0});
}
int len = (1 << (int)ceil(log2(n + m)));
vector<Complex> A = FFT(F, len), B = FFT(G, len), C;
for(int i = 0; i < len; i++){
C.push_back(A[i] * B[i]);
}
vector<Complex> Answer = FFT(C, len, true);
for(int i = 0; i <= n + m; i++){
printf("%.0Lf ", round(Answer[i].Real / (long double)len));
}
putchar('\n');
return 0;
}