提交记录 15042


用户 题目 状态 得分 用时 内存 语言 代码长度
HolyK 1002i. 【模板题】多项式乘法 Accepted 100 71.048 ms 5160 KB C++11 2.55 KB
提交时间 评测时间
2020-11-18 19:48:11 2020-11-18 19:48:16
#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;
}
constexpr int P(998244353), G(3);
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 {
int omega[1 << 21 | 5];
void init(int n) {
  // static int now = 1;
  // omega[1] = 1;
  // while (now < n) {
  //   now <<= 1;
  //   int base = fpow(G, (P - 1) / now);
  //   for (int i = now; i < (now << 1); i++)
  //     omega[i] = i & 1 ? 1LL * omega[i - 1] * base % P : omega[i >> 1];
  // }
}
inline int *alloc(int n) {
  static int mem_pool[1 << 24 | 5], *ptr = mem_pool;
  return ptr += n, ptr - n;
}
struct Polynomial {
  int n, *a;
  Polynomial(int n, int *a): n(n), a(a) {}
  Polynomial(int n): n(n) { a = alloc(n); }
  inline int &operator[](const int &i) { return a[i]; }
  inline const int &operator[](const int &i) const { return a[i]; }
  void dft() {
    for (int k = n >> 1; k; k >>= 1) {
      omega[0] = 1;
      int base = fpow(G, (P - 1) / (k << 1));
      for (int i = 1; i < k; i++) omega[i] = 1LL * omega[i - 1] * base % P;
      for (int i = 0; i < n; i += k << 1) {
        int *p = a + i, *q = p + k, *w = omega;
        for (int j = 0; j < k; j++, p++, q++, w++) {
          int t = *q;
          *q = (1LL * *p - t + P) * *w % P, *p += t;
          if (*p >= P) *p -= P;
        }
      }
    }
  }
  void idft() {
    for (int k = 1; k < n; k <<= 1) {
      omega[0] = 1;
      int base = fpow(G, (P - 1) / (k << 1));
      for (int i = 1; i < k; i++) omega[i] = 1LL * omega[i - 1] * base % P;
      for (int i = 0; i < n; i += k << 1) {
        int *p = a + i, *q = p + k, *w = omega;
        for (int j = 0; j < k; j++, p++, q++, w++) {
          int t = 1LL * *q * *w % P;
          *q = *p - t, *p += t;
          if (*q < 0) *q += P;
          if (*p >= P) *p -= P;
        }
      }
    }
    int inv = fpow(n);
    for (int i = 0; i < n; i++) a[i] = 1LL * a[i] * inv % P;
    std::reverse(a + 1, a + n);
  }
};
} // namespace Polynomial
int main() {
  int n, m, k;
  readInt(n), readInt(m);
  k = 1 << std::__lg(n + m) + 1;
  Polynomial::Polynomial a(k), b(k), c(k);
  for (int i = 0; i <= n; i++) readInt(a[i]);
  for (int i = 0; i <= m; i++) readInt(b[i]);
  Polynomial::init(k);
  a.dft(), b.dft();
  for (int i = 0; i < k; i++) c[i] = 1LL * a[i] * b[i] % P;
  c.idft();
  for (int i = 0; i <= n + m; i++) printf("%d ", c[i]);
  return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #136.12 us44 KBAcceptedScore: 0

Subtask #1 Testcase #271.048 ms4 MB + 984 KBAcceptedScore: 100

Subtask #1 Testcase #332.178 ms2 MB + 68 KBAcceptedScore: 0

Subtask #1 Testcase #432.182 ms2 MB + 56 KBAcceptedScore: 0

Subtask #1 Testcase #539.6 us44 KBAcceptedScore: 0

Subtask #1 Testcase #636.33 us44 KBAcceptedScore: 0

Subtask #1 Testcase #736.86 us44 KBAcceptedScore: 0

Subtask #1 Testcase #865.518 ms4 MB + 716 KBAcceptedScore: 0

Subtask #1 Testcase #965.249 ms4 MB + 716 KBAcceptedScore: 0

Subtask #1 Testcase #1059.963 ms4 MB + 448 KBAcceptedScore: 0

Subtask #1 Testcase #1169.179 ms5 MB + 40 KBAcceptedScore: 0

Subtask #1 Testcase #1249.017 ms3 MB + 944 KBAcceptedScore: 0

Subtask #1 Testcase #1336.1 us44 KBAcceptedScore: 0


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