結果
問題 | No.931 Multiplicative Convolution |
ユーザー |
![]() |
提出日時 | 2019-10-12 06:19:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 104 ms / 2,000 ms |
コード長 | 2,561 bytes |
コンパイル時間 | 1,097 ms |
コンパイル使用メモリ | 106,144 KB |
最終ジャッジ日時 | 2025-01-07 21:57:23 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#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;}