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 53 54 55 56 57 58 59 60 61 62
| #include <bits/stdc++.h> using namespace std;
const double PI = acos(-1); typedef complex<double> Complex; const int maxn = 3e6 + 10;
Complex a[maxn], b[maxn]; int m, n; int bit = 2, rev[maxn];
inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; }
void get_rev(){ while(bit <= n + m) bit <<= 1; for(int i = 0; i < bit; ++i) { rev[i] = (rev[i >> 1] >> 1) | (bit >> 1) * (i & 1); } }
void FFT(Complex *a, int op) { for(int i = 0; i < bit; ++i) { if(i < rev[i]) swap(a[i], a[rev[i]]); } for(int mid = 1; mid < bit; mid <<= 1) { Complex wn = Complex(cos(PI / mid), op * sin(PI / mid)); for(int j = 0; j < bit; j += mid<<1) { Complex w(1, 0); for(int k = 0; k < mid; ++k, w = w * wn) { Complex x = a[j + k], y = w * a[j + k + mid]; a[j + k] = x + y, a[j + k + mid] = x - y; } } } }
int main() { n = read(), m = read(); for(int i = 0; i <= n; ++i) { a[i] = read(); } for(int i = 0; i <= m; ++i) { b[i] = read(); } get_rev(); FFT(a, 1); FFT(b, 1); for(int i = 0; i <= bit; ++i) { a[i] *= b[i]; } FFT(a, -1); for(int i = 0; i <= n + m; ++i) { printf("%d ", (int)(a[i].real() / bit + 0.5)); } printf("\n"); return 0; }
|