求条 T 77
查看原帖
求条 T 77
550775
rsy_楼主2025/1/7 22:32

不是我都和第一篇题解洗的一模一样了,还 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;
}
2025/1/7 22:32
加载中...