結果
問題 | No.931 Multiplicative Convolution |
ユーザー |
![]() |
提出日時 | 2020-08-10 16:39:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#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 200010ll 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;}