//Luogu3803
#include<cstdio>
#include<cmath>
#include<algorithm>
const double PI = acos(-1.0);
const int DFT = 2;
const int IDFT = -2;
struct Complex {
Complex(double real = 0, double imag = 0) : real(real), imag(imag) { }
double real;
double imag;
Complex operator*(const Complex &cmplx) const {
return (Complex){real * cmplx.real - imag * cmplx.imag,
real * cmplx.imag + imag * cmplx.real};
}
Complex operator+(const Complex &cmplx) const {
return (Complex){real + cmplx.real, imag + cmplx.imag};
}
Complex operator-(const Complex &cmplx) const {
return (Complex){real - cmplx.real, imag - cmplx.imag};
}
};
void FFT(Complex arr[], int limit, int mode) {
for(int i = 0, j = 0; i < limit; ++i) {
if(i > j) std::swap(arr[i], arr[j]);
int bin = limit >> 1;
while((j ^= bin) < bin) bin >>= 1;
}
for(int len = 2; len <= limit; len <<= 1) {
Complex lenUnitRoot(std::cos(2 * PI / len), sin(mode * PI / len));
int mid = len >> 1;
for(int i = 0; i < limit; i += len) {
Complex nowX(1, 0);
for(int j = i; j < i + mid; ++j) {
Complex left = arr[j];
Complex right = nowX * arr[j + mid];
arr[j] = left + right;
arr[j + mid] = left - right;
nowX = nowX * lenUnitRoot;
}
}
}
if(mode == IDFT) {
for(int i = 0; i < limit; ++i) {
arr[i].real = int(arr[i].real / limit + 0.5);
arr[i].imag = 0;
}
}
return;
}
int main() {
int len1, len2;
scanf("%d%d", &len1, &len2);
int limit = 1;
while(limit <= len1 + len2) {
limit <<= 1;
}
Complex *arr1 = new Complex[limit];
Complex *arr2 = new Complex[limit];
for(int i = 0; i <= len1; ++i) {
scanf("%lf", &arr1[i].real);
}
for(int i = 0; i <= len2; ++i) {
scanf("%lf", &arr2[i].real);
}
FFT(arr1, limit, DFT);
FFT(arr2, limit, DFT);
for(int i = 0; i < limit; ++i) {
arr1[i] = arr1[i] * arr2[i];
}
FFT(arr1, limit, IDFT);
for(int i = 0; i <= len1 + len2; ++i) {
printf("%d ", (int)(arr1[i].real));
}
return 0;
}
FFT
Share