不是我都和第一篇题解洗的一模一样了,还 T 了。
#include <bits/stdc++.h>
#define lb(x) (x&-x)
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
using namespace std;
using i64 = long long;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
void chmin(int &x, int c) {x = min(x, c);}
void chmax(int &x, int c) {x = max(x, c);}
const int maxn = 4e6 + 10, mod = 998244353;
const double pi = acos(-1);
struct Complex {
double x, y;
Complex (double xx = 0, double yy = 0) {
x = xx, y = yy;
}
} A[maxn], B[maxn];
Complex operator + (Complex a, Complex b) {
return Complex (a.x + b.x, a.y + b.y);
}
Complex operator - (Complex a, Complex b) {
return Complex (a.x - b.x, a.y - b.y);
}
Complex operator * (Complex a, Complex b) {
return Complex (a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
int N, M, limit = 1, rev[maxn];
void fft (Complex *A, int opt) {
for (int i = 0; i < limit; i ++ )
if (i < rev[i])
swap (A[rev[i]], A[i]);
for (int mid = 1; mid < limit; mid <<= 1) {
Complex w1 (cos(pi / mid), opt * sin(pi / mid));
for (int j = 0; j < limit; j += (mid << 1)) {
Complex w(1, 0);
for (int k = 0; k < mid; k ++, w = w * w1) {
Complex x = A[j + k], y = w * A[j + k + mid];
A[j + k] = x + y;
A[j + k + mid] = x - y;
}
}
}
}
void solve() {
cin >> N >> M;
for (int i = 0, x; i <= N; i ++ ) cin >> x, A[i].x = x;
for (int i = 0, x; i <= M; i ++ ) cin >> x, B[i].x = x;
int count = 0;
while (limit <= N + M) limit <<= 1, count ++ ;
for (int i = 0; i < limit; i ++ )
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (count - 1));
fft (A, 1), fft (B, 1);
for (int i = 0; i <= limit; i ++ ) A[i] = A[i] * B[i];
fft (A, -1);
for (int i = 0; i <= N + M; i ++ )
cout << (int)(A[i].x / limit + 0.1) << ' ';
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T--)solve();
return 0;
}