結果

問題 No.931 Multiplicative Convolution
ユーザー goodbatongoodbaton
提出日時 2020-08-10 16:39:02
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 210 ms / 2,000 ms
コード長 4,089 bytes
コンパイル時間 1,170 ms
コンパイル使用メモリ 106,548 KB
実行使用メモリ 8,576 KB
最終ジャッジ日時 2024-10-07 22:35:00
合計ジャッジ時間 4,446 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 3 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 3 ms
5,248 KB
testcase_06 AC 3 ms
5,248 KB
testcase_07 AC 23 ms
5,888 KB
testcase_08 AC 208 ms
8,576 KB
testcase_09 AC 191 ms
8,448 KB
testcase_10 AC 206 ms
8,448 KB
testcase_11 AC 197 ms
8,320 KB
testcase_12 AC 194 ms
7,808 KB
testcase_13 AC 207 ms
8,320 KB
testcase_14 AC 210 ms
8,576 KB
testcase_15 AC 210 ms
8,576 KB
testcase_16 AC 207 ms
8,448 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>
#include <bitset>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include <cassert>
#include <functional>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(...) ;
#else
#define debug(...) cerr << __LINE__ << " : " << #__VA_ARGS__ << " = " << _tostr(__VA_ARGS__) << endl;

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v);

template<typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}

void _tostr_rec(ostringstream &oss) {
  oss << "\b\b \b";
}

template<typename Head, typename... Tail>
void _tostr_rec(ostringstream &oss, Head &&head, Tail &&... tail) {
  oss << head << ", ";
  _tostr_rec(oss, forward<Tail>(tail)...);
}

template<typename... T>
string _tostr(T &&... args) {
  ostringstream oss;
  int size = sizeof...(args);
  if (size > 1) oss << "{";
  _tostr_rec(oss, forward<T>(args)...);
  if (size > 1) oss << "}";
  return oss.str();
}
#endif

// #define mod 1000000007 //1e9+7(prime number)
#define mod 998244353
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

ll power(ll k, ll n, int M) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * k % M;
    k = k * k % M;
    n /= 2;
  }
  return res;
}

ll getPrimitiveRoot(ll P) {
  if (P == 2) return 1;
  // assert(isPrime(P) && P >= 3);
  ll p = P - 1;
  vector<ll> a;

  for (int i = 2; i * i <= p; i++) {
    if (p % i == 0) a.push_back(i);
    while (p % i == 0) p /= i;
  }
  if (p > 1) a.push_back(p);

  while (1) {
    bool ok = true;
    ll r = rand() % (P - 2) + 2;
    for (auto q : a)
      ok &= power(r, (P - 1) / q, P) != 1;
    if (ok) return r;
  }
}

/* Number Theoretic Transform */

namespace NTT {
  void DFT(int m, int root, vector<int> &a, bool rev = false) {
    int N = a.size();

    for (int i = 0, j = 1; j + 1 < N; j++) {
      for (int k = N >> 1; k > (i ^= k); k >>= 1)
        ;
      if (i > j) swap(a[i], a[j]);
    }

    int g = power(root, (m - 1) / N, m);
    if (rev) g = power(g, m - 2, m);

    for (int i = 1; i < N; i *= 2) {
      int base = power(g, N / i / 2, m);
      ll w = 1;
      for (int j = 0; j < i; j++) {
        for (int k = 0; k < N; k += i * 2) {
          int s = a[j + k], t = a[j + k + i] * w % m;
          a[j + k + 0] = (s + t) % m;
          a[j + k + i] = (s - t + m) % m;
        }
        w = w * base % m;
      }
    }

    if (rev) {
      ll tmp = power(N, m - 2, m);
      for (int &v : a) v = v * tmp % m;
    }
  }

  // (469762049, 3), (924844033, 5), (998244353, 3), (1012924417, 5)

  vector<int> conv(int _mod, int root, const vector<int> &a, const vector<int> &b) {
    int s = 1, t = a.size() + b.size() - 1;
    while (s < t) s *= 2;

    vector<int> F(s), G(s);
    for (int i = 0; i < (int)a.size(); i++) F[i] = a[i];
    for (int i = 0; i < (int)b.size(); i++) G[i] = b[i];
    DFT(_mod, root, F);
    DFT(_mod, root, G);

    for (int i = 0; i < s; i++) F[i] = (ll)F[i] * G[i] % _mod;
    DFT(_mod, root, F, true);

    return F;
  }
};

int main() {
  int P, A[SIZE], B[SIZE];
  ll ans[SIZE] = {};

  scanf("%d", &P);

  for (int i = 1; i < P; i++) scanf("%d", A + i);
  for (int i = 1; i < P; i++) scanf("%d", B + i);

  ll R = getPrimitiveRoot(P);

  vector<int> v1(P), v2(P);

  ll t = 1;
  for (int i = 0; i < P - 1; i++) {
    v1[i] = A[t];
    v2[i] = B[t];
    t = t * R % P;
  }

  auto v = NTT::conv(mod, 3, v1, v2);

  t = 1;
  for (auto p : v) {
    ans[t] += p;
    t = t * R % P;
  }

  for (int i = 1; i < P; i++) {
    printf("%lld%c", ans[i] % mod, " \n"[i + 1 == P]);
  }


  return 0;
}
0