結果
問題 | No.931 Multiplicative Convolution |
ユーザー |
![]() |
提出日時 | 2024-05-28 12:12:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 2,069 bytes |
コンパイル時間 | 3,380 ms |
コンパイル使用メモリ | 233,596 KB |
最終ジャッジ日時 | 2025-02-21 17:02:34 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/convolution>#include <atcoder/modint>using namespace atcoder;using mint = modint998244353;void fast_io() {ios_base::sync_with_stdio(false);cin.tie(nullptr);}int main() {fast_io();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];}if (p == 2) {cout << (mint(a[1]) * b[1]).val() << "\n";return 0;}// prime factorization of p - 1vector<int> pf;{int tmp = p - 1;for (int i = 2; i * i <= tmp; i++) {if (tmp % i == 0) {pf.push_back(i);while (tmp % i == 0) {tmp /= i;}}}if (tmp > 1) {pf.push_back(tmp);}}auto pow_mod = [&](int x, int n) {int res = 1;while (n > 0) {if (n & 1) {res = (long long)res * x % p;}x = (long long)x * x % p;n >>= 1;}return res;};// find a primitive rootint pr = -1;for (int i = 2; i < p; i++) {bool ok = true;for (int j : pf) {if (pow_mod(i, (p - 1) / j) == 1) {ok = false;break;}}if (ok) {pr = i;break;}}assert(pr > 1);vector<int> gr(p), logp(p);int cur = 1;for (int i = 0; i < p - 1; i++) {gr[cur] = i;logp[i] = cur;cur = (long long)cur * pr % p;}vector<mint> f(p - 1), g(p - 1);for (int i = 1; i < p; i++) {f[gr[i]] = a[i];g[gr[i]] = b[i];}auto h = convolution(f, g);vector<mint> ans(p);for (int i = 0; i < h.size(); i++) {ans[logp[i % (p - 1)]] += h[i];}for (int i = 1; i < p; i++) {cout << ans[i].val() << " ";}cout << "\n";}