提交记录 15068


用户 题目 状态 得分 用时 内存 语言 代码长度
HolyK 1002. 测测你的多项式乘法 Compile Error 0 0 ns 0 KB C++11 2.43 KB
提交时间 评测时间
2020-11-19 10:33:04 2020-11-19 10:33:06
#include <bits/stdc++.h>
template <class T>
inline void readInt(T &w) {
  char c, p = 0;
  while (!isdigit(c = getchar())) p = c == '-';
  for (w = c & 15; isdigit(c = getchar());) w = w * 10 + (c & 15);
  if (p) w = -w;
}
template <class T, class... U>
inline void readInt(T &w, U &... a) { readInt(w), readInt(a...); }

constexpr int P(998244353), G(3);
inline void inc(int &x, int y) { (x += y) >= P ? x -= P : 0; }
inline int sum(int x, int y) { return x + y >= P ? x + y - P : x + y; }
inline int sub(int x, int y) { return x - y < 0 ? x - y + P : x - y; }
inline int fpow(int x, int k = P - 2) {
  int r = 1;
  for (; k; k >>= 1, x = 1LL * x * x % P)
    if (k & 1) r = 1LL * r * x % P;
  return r;
}


namespace Polynomial {
using Polynom = std::vector<int>;
int n;
std::vector<int> w;
void getOmega(int k) {
  w.resize(k);
  w[0] = 1;
  int base = fpow(G, (P - 1) / (k << 1));
  for (int i = 1; i < k; i++) w[i] = 1LL * w[i - 1] * base % P;
}
void dft(Polynom &a) {
  for (int k = n >> 1; k; k >>= 1) {
    getOmega(k);
    for (int i = 0; i < n; i += k << 1) {
      for (int j = 0; j < k; j++) {
        int y = a[i + j + k];
        a[i + j + k] = (1LL * a[i + j] - y + P) * w[j] % P;
        inc(a[i + j], y);
      }
    }
  }
}
void idft(Polynom &a) {
  for (int k = 1; k < n; k <<= 1) {
    getOmega(k);
    for (int i = 0; i < n; i += k << 1) {
      for (int j = 0; j < k; j++) {
        int x = a[i + j], y = 1LL * a[i + j + k] * w[j] % P;
        a[i + j] = sum(x, y);
        a[i + j + k] = sub(x, y);
      }
    }
  }
  int inv = fpow(n);
  for (int i = 0; i < n; i++) a[i] = 1LL * a[i] * inv % P;
  std::reverse(a.begin() + 1, a.end());
}
} // namespace Polynom
using Polynomial::dft;
using Polynomial::idft;
void poly_multiply(unsigned *A, int n, unsigned *B, int m, unsigned *C) {
  int k = Polynomial::n = 1 << std::__lg(n + m) + 1;
  std::vector<int> a(k), b(k);
  for (int i = 0; i <= n; i++) a[i] = A[i];
  for (int i = 0; i <= m; i++) b[i] = B[i];
  dft(a), dft(b);
  for (int i = 0; i < k; i++) a[i] = 1LL * a[i] * b[i] % P;
  idft(a);
  for (int i = 0; i <= n + m; i++) C[i] = a[i];
}
int main() {
  int n, m, k;
  readInt(n, m);
  Polynomial::n = k = 1 << std::__lg(n + m) + 1;
  std::vector<int> a(k), b(k);
  for (int i = 0; i <= n; i++) readInt(a[i]);
  for (int i = 0; i <= m; i++) readInt(b[i]);
  dft(a), dft(b);
  for (int i = 0; i < k; i++) a[i] = 1LL * a[i] * b[i] % P;
  idft(a);
  for (int i = 0; i <= n + m; i++) printf("%d ", a[i]);
  return 0;
}

CompilationN/AN/ACompile ErrorScore: N/A


Judge Duck Online | 评测鸭在线
Server Time: 2026-03-21 11:05:23 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠