結果
問題 | No.931 Multiplicative Convolution |
ユーザー | kazuma |
提出日時 | 2019-11-23 12:52:04 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 179 ms / 2,000 ms |
コード長 | 3,117 bytes |
コンパイル時間 | 2,332 ms |
コンパイル使用メモリ | 207,888 KB |
実行使用メモリ | 8,196 KB |
最終ジャッジ日時 | 2024-10-11 06:55:15 |
合計ジャッジ時間 | 4,807 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 3 ms
5,248 KB |
testcase_07 | AC | 18 ms
5,248 KB |
testcase_08 | AC | 176 ms
8,196 KB |
testcase_09 | AC | 122 ms
7,960 KB |
testcase_10 | AC | 170 ms
7,900 KB |
testcase_11 | AC | 121 ms
7,944 KB |
testcase_12 | AC | 134 ms
7,272 KB |
testcase_13 | AC | 171 ms
7,856 KB |
testcase_14 | AC | 179 ms
8,068 KB |
testcase_15 | AC | 178 ms
8,068 KB |
testcase_16 | AC | 172 ms
7,952 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int mod_inv(ll a, ll m) { ll b = m, u = 1, v = 0; while (b > 0) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } return (u % m + m) % m; } ll mod_pow(ll x, ll y, ll md) { ll res = 1; while (y) { if (y & 1) res = res * x % md; x = x * x % md; y >>= 1; } return res; } template <int Mod, int PrimitiveRoot> class fast_modulo_transform { public: static vector<int> fft(vector<int> v, bool inv) { const int N = v.size(); assert((N ^ (N & -N)) == 0); int ww = mod_pow(PrimitiveRoot, (Mod - 1) / N, Mod); if (inv) ww = mod_inv(ww, Mod); for (int m = N; m >= 2; m >>= 1) { const int mh = m >> 1; int w = 1; for (int i = 0; i < mh; ++i) { for (int j = i; j < N; j += m) { const int k = j + mh; int x = v[j] - v[k]; if (x < 0) x += Mod; v[j] += -Mod + v[k]; if (v[j] < 0) v[j] += Mod; v[k] = (1LL * w * x) % Mod; } w = (1LL * w * ww) % Mod; } ww = (1LL * ww * ww) % Mod; } int i = 0; for (int j = 1; j < N - 1; ++j) { for (int k = N >> 1; k >(i ^= k); k >>= 1); if (j < i) swap(v[i], v[j]); } if (inv) { const int inv_n = mod_inv(N, Mod); for (auto& x : v) { x = (1LL * x * inv_n) % Mod; assert(0 <= x && x < Mod); } } return v; } static vector<int> convolution(vector<int> f, vector<int> g) { int sz = 1; const int m = f.size() + g.size() - 1; while (sz < m) sz *= 2; f.resize(sz), g.resize(sz); f = fast_modulo_transform::fft(move(f), false); g = fast_modulo_transform::fft(move(g), false); for (int i = 0; i < sz; ++i) { f[i] = (1LL * f[i] * g[i]) % Mod; } return fast_modulo_transform::fft(move(f), true); } }; const int mod = 998244353; using fmt = fast_modulo_transform<998244353, 3>; int mod_pow(int a, int b, int m) { int ret = 1; while (b) { if (b & 1) ret = 1LL * ret * a % m; a = 1LL * a * a % m; b >>= 1; } return ret; } template <typename T> T get_primitive_root(T p) { // p is prime vector<T> fac; T v = p - 1; for (T pp = 2; pp * pp <= v; pp++) if (v % pp == 0) { while (v % pp == 0) v /= pp; fac.push_back(pp); } if (v > 1) fac.push_back(v); for (T g = 2; g < p; g++) { assert(mod_pow(g, p - 1, p) == 1); bool ok = true; for (auto pp : fac) { if (mod_pow(g, (p - 1) / pp, p) == 1) { ok = false; break; } } if (ok) return g; } return -1; } int main() { int P; cin >> P; vector<int> A(P), B(P); for (int i = 1; i < P; i++) { cin >> A[i]; } for (int i = 1; i < P; i++) { cin >> B[i]; } int rt = get_primitive_root(P); vector<int> v(P), pos(P); for (int i = 0; i < P - 1; i++) { int x = mod_pow(rt, i, P); v[i] = x; pos[x] = i; } vector<int> a(P), b(P); for (int i = 0; i < P - 1; i++) { a[i] = A[v[i]]; b[i] = B[v[i]]; } auto c = fmt::convolution(a, b); for (int i = P - 1; i < (int)c.size(); i++) { (c[i % (P - 1)] += c[i]) %= mod; } vector<int> C(P); for (int i = 0; i < P - 1; i++) { C[v[i]] = c[i]; } for (int i = 1; i < P; i++) { cout << C[i] << " \n"[i + 1 == P]; } return 0; }