結果
問題 | No.931 Multiplicative Convolution |
ユーザー |
|
提出日時 | 2020-08-19 08:34:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,342 ms / 2,000 ms |
コード長 | 7,554 bytes |
コンパイル時間 | 2,249 ms |
コンパイル使用メモリ | 136,444 KB |
最終ジャッジ日時 | 2025-01-13 03:40:37 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
/*** author: otera**/#include<iostream>#include<string>#include<cstdio>#include<cstring>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<deque>#include<ciso646>#include<random>#include<map>#include<set>#include<complex>#include<bitset>#include<stack>#include<unordered_map>#include<unordered_set>#include<utility>#include<cassert>using namespace std;#define int long longtypedef long long ll;typedef unsigned long long ul;typedef unsigned int ui;typedef long double ld;const int inf=1e9+7;const ll INF=1LL<<60 ;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define rep1(i,n) for(int i=1;i<=n;i++)#define per1(i,n) for(int i=n;i>=1;i--)#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)typedef complex<ld> Point;const ld eps = 1e-8;const ld pi = acos(-1.0);typedef pair<int, int> P;typedef pair<ld, ld> LDP;typedef pair<ll, ll> LP;#define fr first#define sc second#define all(c) c.begin(),c.end()#define pb push_back#define debug(x) cerr << #x << " = " << (x) << endl;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}long long modinv(long long a, long long mod) {long long b = mod, u = 1, v = 0;while (b) {long long t = a/b;a -= t*b; swap(a, b);u -= t*v; swap(u, v);}u %= mod;if (u < 0) u += mod;return u;}const int MOD = 998244353;namespace NTT {// const int MOD = 998244353; // to be set appropriatelyconst long long PR = 3; // to be set appropriatelyvoid trans(vector<long long> &v, bool inv = false) {int n = (int)v.size();for (int i = 0, j = 1; j < n-1; j++) {for (int k = n>>1; k > (i ^= k); k >>= 1);if (i > j) swap(v[i], v[j]);}for (int t = 2; t <= n; t <<= 1) {long long bw = modpow(PR, (MOD-1)/t, MOD);if (inv) bw = modinv(bw, MOD);for (int i = 0; i < n; i += t) {long long w = 1;for (int j = 0; j < t/2; ++j) {int j1 = i + j, j2 = i + j + t/2;long long c1 = v[j1], c2 = v[j2] * w % MOD;v[j1] = c1 + c2;v[j2] = c1 - c2 + MOD;while (v[j1] >= MOD) v[j1] -= MOD;while (v[j2] >= MOD) v[j2] -= MOD;w = w * bw % MOD;}}}if (inv) {long long inv_n = modinv(n, MOD);for (int i = 0; i < n; ++i) v[i] = v[i] * inv_n % MOD;}}// C is A*Bvector<long long> mult(vector<long long> A, vector<long long> B) {int size_a = 1; while (size_a < A.size()) size_a <<= 1;int size_b = 1; while (size_b < B.size()) size_b <<= 1;int size_fft = max(size_a, size_b) << 1;vector<long long> cA(size_fft, 0), cB(size_fft, 0), cC(size_fft, 0);for (int i = 0; i < A.size(); ++i) cA[i] = A[i];for (int i = 0; i < B.size(); ++i) cB[i] = B[i];trans(cA); trans(cB);for (int i = 0; i < size_fft; ++i) cC[i] = cA[i] * cB[i] % MOD;trans(cC, true);vector<long long> res((int)A.size() + (int)B.size() - 1);for (int i = 0; i < res.size(); ++i) res[i] = cC[i];return res;}};ll get_root(ll p) {for(int r = 2; r < p; ++ r) {int x = 1;set<int> se;while(true) {if(se.size() == p - 1) return r;if(se.count(x)) break;se.insert(x);x = x * r % p;}}assert(false);}struct ComplexNumber {double real, imag;inline ComplexNumber& operator = (const ComplexNumber &c) {real = c.real; imag = c.imag; return *this;}friend inline ostream& operator << (ostream &s, const ComplexNumber &c) {return s<<'<'<<c.real<<','<<c.imag<<'>';}};inline ComplexNumber operator + (const ComplexNumber &x, const ComplexNumber &y) {return {x.real + y.real, x.imag + y.imag};}inline ComplexNumber operator - (const ComplexNumber &x, const ComplexNumber &y) {return {x.real - y.real, x.imag - y.imag};}inline ComplexNumber operator * (const ComplexNumber &x, const ComplexNumber &y) {return {x.real * y.real - x.imag * y.imag, x.real * y.imag + x.imag * y.real};}inline ComplexNumber operator * (const ComplexNumber &x, double a) {return {x.real * a, x.imag * a};}inline ComplexNumber operator / (const ComplexNumber &x, double a) {return {x.real / a, x.imag / a};}const int MAX = 1<<19; // must be 2^nstruct FFT {vector<ComplexNumber> AT, BT, CT;void DTM(vector<ComplexNumber> &F, bool inv) {int N = MAX;for (int t = N; t >= 2; t >>= 1) {double ang = acos(-1.0)*2/t;for (int i = 0; i < t/2; i++) {ComplexNumber w = {cos(ang*i), sin(ang*i)};if (inv) w.imag = -w.imag;for (int j = i; j < N; j += t) {ComplexNumber f1 = F[j] + F[j+t/2];ComplexNumber f2 = (F[j] - F[j+t/2]) * w;F[j] = f1;F[j+t/2] = f2;}}}for (int i = 1, j = 0; i < N; i++) {for (int k = N >> 1; k > (j ^= k); k >>= 1);if (i < j) swap(F[i], F[j]);}}// C is A*Bvoid mult(vector<long long> &A, vector<long long> &B, vector<long long> &C) {AT.assign(MAX, {0.0, 0.0});BT.assign(MAX, {0.0, 0.0});CT.assign(MAX, {0.0, 0.0});for (int i = 0; i < MAX; ++i) AT[i] = {(double)A[i], 0.0};for (int i = 0; i < MAX; ++i) BT[i] = {(double)B[i], 0.0};DTM(AT, false);DTM(BT, false);for (int i = 0; i < MAX; ++i) CT[i] = AT[i] * BT[i];DTM(CT, true);for (int i = 0; i < MAX; ++i) {CT[i] = CT[i] / MAX;C[i] = (long long)(CT[i].real + 0.5);}}};void solve() {int p; cin >> p;// vector<int> a(MAX, 0), b(MAX, 0);vector<int> a(p, 0), b(p, 0);rep(i, p - 1) {cin >> a[i + 1];}rep(i, p - 1) {cin >> b[i + 1];}if(p == 2) {cout << a[1] * b[1] % MOD << endl;return;}int r = get_root(p);vector<int> x(1<<17), y(1<<17);int v = 1;rep(i, p - 1) {x[i] = a[v], y[i] = b[v]; // v = r ^ i// cerr << v << " ";v = v * r % p;}// cerr << endl;auto z = NTT::mult(x, y);// vector<int> c(MAX);// FFT fft;// fft.mult(a, b, c);vector<int> ans(p, 0);v = 1;rep(i, (int)z.size()) {ans[v] += z[i]; // v = r ^ i// ans[v] += c[i];ans[v] %= MOD;v = v * r % p;}for(int i = 1; i <= p - 1; ++ i) {cout << ans[i] << " ";}cout << endl;}signed main() {ios::sync_with_stdio(false);cin.tie(0);//cout << fixed << setprecision(10);//int t; cin >> t; rep(i, t)solve();solve();return 0;}