結果
問題 | No.931 Multiplicative Convolution |
ユーザー | otera |
提出日時 | 2020-08-19 08:34:36 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 798 ms / 2,000 ms |
コード長 | 7,554 bytes |
コンパイル時間 | 1,679 ms |
コンパイル使用メモリ | 142,288 KB |
実行使用メモリ | 20,608 KB |
最終ジャッジ日時 | 2024-10-12 03:34:05 |
合計ジャッジ時間 | 6,407 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 65 ms
15,360 KB |
testcase_01 | AC | 78 ms
15,488 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 70 ms
15,488 KB |
testcase_04 | AC | 76 ms
15,488 KB |
testcase_05 | AC | 97 ms
15,616 KB |
testcase_06 | AC | 114 ms
15,488 KB |
testcase_07 | AC | 137 ms
16,000 KB |
testcase_08 | AC | 252 ms
19,712 KB |
testcase_09 | AC | 119 ms
19,328 KB |
testcase_10 | AC | 225 ms
20,224 KB |
testcase_11 | AC | 225 ms
20,096 KB |
testcase_12 | AC | 186 ms
18,560 KB |
testcase_13 | AC | 798 ms
20,352 KB |
testcase_14 | AC | 373 ms
20,608 KB |
testcase_15 | AC | 258 ms
18,560 KB |
testcase_16 | AC | 241 ms
19,328 KB |
ソースコード
/** * 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 long typedef 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 appropriately const long long PR = 3; // to be set appropriately void 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*B vector<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^n struct 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*B void 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; }