結果
問題 | No.931 Multiplicative Convolution |
ユーザー | pockyny |
提出日時 | 2019-10-12 06:19:31 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 109 ms / 2,000 ms |
コード長 | 2,561 bytes |
コンパイル時間 | 1,165 ms |
コンパイル使用メモリ | 107,704 KB |
実行使用メモリ | 12,524 KB |
最終ジャッジ日時 | 2024-10-11 02:39:58 |
合計ジャッジ時間 | 3,763 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 66 ms
9,448 KB |
testcase_01 | AC | 67 ms
9,448 KB |
testcase_02 | AC | 66 ms
9,448 KB |
testcase_03 | AC | 66 ms
9,444 KB |
testcase_04 | AC | 67 ms
9,320 KB |
testcase_05 | AC | 64 ms
9,456 KB |
testcase_06 | AC | 66 ms
9,468 KB |
testcase_07 | AC | 70 ms
9,920 KB |
testcase_08 | AC | 109 ms
12,160 KB |
testcase_09 | AC | 94 ms
12,204 KB |
testcase_10 | AC | 104 ms
12,000 KB |
testcase_11 | AC | 93 ms
12,216 KB |
testcase_12 | AC | 92 ms
11,512 KB |
testcase_13 | AC | 103 ms
12,064 KB |
testcase_14 | AC | 106 ms
12,112 KB |
testcase_15 | AC | 106 ms
12,524 KB |
testcase_16 | AC | 105 ms
12,140 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <random> using namespace std; typedef long long ll; const ll mod = 998244353; template<class T> T extgcd(T a, T b, T& x, T& y) { for (T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; } template<class T> T mod_inv(T a, T m) { T x, y; extgcd(a, m, x, y); return (m + x % m) % m; } ll pw(ll a, ll b){ ll x = 1; while (b){ while(!(b&1)){ (a *= a) %= mod; b /= 2; } (x *= a) %= mod; b--; } return x; } void _ntt(vector <ll> &a,int sign) { int i,j,k,n = a.size(),m = 1; while(m<n || m==1) m <<= 1; a.resize(m); n = m; const int g = 3; ll h = pw(g,(mod - 1)/n); if(sign==-1) h = (int)mod_inv(h,mod); i = 0; for(j=1;j<n - 1;j++) { for(k=(n >> 1); k>(i ^= k); k >>= 1); if(j<i) swap(a[i],a[j]); } for(i=1;i<n;i*= 2){ const int i2 = 2*i; const ll base = pw(h,n/i2); ll w = 1; for(j=0;j<i;j++){ for(k=j;k<n;k += i2){ ll u = a[k],d = a[k + i]*w%mod; a[k] = u + d; if(a[k]>=mod) a[k] -= mod; a[k + i] = u - d; if(a[k + i]<0) a[k + i] += mod; } (w *= base) %= mod; } } for(ll x: a){ if(x<0) x += mod; } } void ntt(vector<ll>& input) { _ntt(input, 1); } void intt(vector<ll>& input) { _ntt(input, -1); ll x = input.size(); const int n_inv = mod_inv(x, mod); for (auto& x : input) (x *= n_inv) %= mod; } ll a[140000] = {},b[140000] = {},ans[100010],c[200010]; int p,gen = -1; bool gensi(ll g){ int i; ll ret = 1; for(i=1;i<p - 1;i++){ (ret *= g) %= p; if(ret==1) return false; } return true; } vector<ll> u(262144),v(262144); int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int i; cin >> p; for(i=1;i<p;i++) cin >> a[i]; for(i=1;i<p;i++) cin >> b[i]; vector<ll> w; for(i=1;i<p;i++) w.push_back(i); random_device seed_gen; mt19937 engine(seed_gen()); shuffle(w.begin(),w.end(),engine); for(i=0;i<p - 1;i++){ if(gensi(w[i])){ gen = w[i]; break; } } ll j = 1; for(i=0;i<p - 1;i++){ u[i] = a[j]; v[i] = b[j]; (j *= gen) %= p; } j = 1; for(i=0;i<2*p;i++){ c[i] = j; (j *= gen) %= p; } ntt(u); ntt(v); for(i=0;i<262144;i++){ (u[i] *= v[i]) %= mod; } intt(u); for(i=0;i<2*p;i++){ (ans[c[i]] += u[i]) %= mod; } for(i=1;i<=p - 1;i++){ cout << ans[i] << " "; } cout << endl; }