結果
問題 | No.931 Multiplicative Convolution |
ユーザー | beet |
提出日時 | 2019-11-22 22:21:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 215 ms / 2,000 ms |
コード長 | 5,267 bytes |
コンパイル時間 | 3,138 ms |
コンパイル使用メモリ | 220,480 KB |
最終ジャッジ日時 | 2025-01-08 05:12:50 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 4 ms
5,248 KB |
testcase_07 | AC | 21 ms
6,400 KB |
testcase_08 | AC | 205 ms
30,724 KB |
testcase_09 | AC | 184 ms
30,528 KB |
testcase_10 | AC | 207 ms
30,416 KB |
testcase_11 | AC | 184 ms
30,208 KB |
testcase_12 | AC | 165 ms
28,312 KB |
testcase_13 | AC | 204 ms
30,400 KB |
testcase_14 | AC | 215 ms
30,852 KB |
testcase_15 | AC | 215 ms
30,944 KB |
testcase_16 | AC | 203 ms
30,440 KB |
ソースコード
#include<bits/stdc++.h>using namespace std;using Int = long long;template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}struct FastIO{FastIO(){cin.tie(0);ios::sync_with_stdio(0);}}fastio_beet;template<typename T>T mod_pow(T a,long long n,T mod){using ll = long long;T res(1);while(n){if(n&1) res=(ll)res*a%mod;a=(ll)a*a%mod;n>>=1;}return res;}template<typename T>map<T, Int> factorize(T x){map<T, Int> res;for(Int i=2;i*i<=x;i++){while(x%i==0){x/=i;res[i]++;}}if(x!=1) res[x]++;return res;}template<typename T>T order(T x,T MOD){static map<T, vector<T>> dp;vector<T> &ps=dp[MOD];if(ps.empty()){auto fs=factorize(MOD-1);for(auto p:fs) ps.emplace_back(p.first);}T res=MOD-1;for(T p:ps){while(res%p==0){if(mod_pow(x,res/p,MOD)!=1) break;res/=p;}}return res;}template<typename T,T MOD = 1000000007>struct Mint{static constexpr T mod = MOD;T v;Mint():v(0){}Mint(signed v):v(v){}Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}Mint pow(long long k){Mint res(1),tmp(v);while(k){if(k&1) res*=tmp;tmp*=tmp;k>>=1;}return res;}static Mint add_identity(){return Mint(0);}static Mint mul_identity(){return Mint(1);}Mint inv(){return pow(MOD-2);}Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}Mint& operator/=(Mint a){return (*this)*=a.inv();}Mint operator+(Mint a) const{return Mint(v)+=a;}Mint operator-(Mint a) const{return Mint(v)-=a;}Mint operator*(Mint a) const{return Mint(v)*=a;}Mint operator/(Mint a) const{return Mint(v)/=a;}Mint operator-() const{return v?Mint(MOD-v):Mint(v);}bool operator==(const Mint a)const{return v==a.v;}bool operator!=(const Mint a)const{return v!=a.v;}bool operator <(const Mint a)const{return v <a.v;}static Mint comb(long long n,Int k){Mint num(1),dom(1);for(Int i=0;i<k;i++){num*=Mint(n-i);dom*=Mint(i+1);}return num/dom;}};template<typename T,T MOD> constexpr T Mint<T, MOD>::mod;template<typename T,T MOD>ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;}constexpr Int bmds(Int x){const Int v[] = {1012924417, 924844033, 998244353,897581057, 645922817};return v[x];}constexpr Int brts(Int x){const Int v[] = {5, 5, 3, 3, 3};return v[x];}template<Int X>struct NTT{static constexpr Int md = bmds(X);static constexpr Int rt = brts(X);using M = Mint<Int, md>;vector< vector<M> > rts,rrts;void ensure_base(Int n){if((Int)rts.size()>=n) return;rts.resize(n);rrts.resize(n);for(Int i=1;i<n;i<<=1){if(!rts[i].empty()) continue;M w=M(rt).pow((md-1)/(i<<1));M rw=w.inv();rts[i].resize(i);rrts[i].resize(i);rts[i][0]=M(1);rrts[i][0]=M(1);for(Int k=1;k<i;k++){rts[i][k]=rts[i][k-1]*w;rrts[i][k]=rrts[i][k-1]*rw;}}}void ntt(vector<M> &as,bool f,Int n=-1){if(n==-1) n=as.size();assert((n&(n-1))==0);ensure_base(n);for(Int i=0,j=1;j+1<n;j++){for(Int k=n>>1;k>(i^=k);k>>=1);if(i>j) swap(as[i],as[j]);}for(Int i=1;i<n;i<<=1){for(Int j=0;j<n;j+=i*2){for(Int k=0;k<i;k++){M z=as[i+j+k]*(f?rrts[i][k]:rts[i][k]);as[i+j+k]=as[j+k]-z;as[j+k]+=z;}}}if(f){M tmp=M(n).inv();for(Int i=0;i<n;i++) as[i]*=tmp;}}vector<M> multiply(vector<M> as,vector<M> bs){Int need=as.size()+bs.size()-1;Int sz=1;while(sz<need) sz<<=1;as.resize(sz,M(0));bs.resize(sz,M(0));ntt(as,0);ntt(bs,0);for(Int i=0;i<sz;i++) as[i]*=bs[i];ntt(as,1);as.resize(need);return as;}vector<Int> multiply(vector<Int> as,vector<Int> bs){vector<M> am(as.size()),bm(bs.size());for(Int i=0;i<(Int)am.size();i++) am[i]=M(as[i]);for(Int i=0;i<(Int)bm.size();i++) bm[i]=M(bs[i]);vector<M> cm=multiply(am,bm);vector<Int> cs(cm.size());for(Int i=0;i<(Int)cs.size();i++) cs[i]=cm[i].v;return cs;}};template<Int X> constexpr Int NTT<X>::md;template<Int X> constexpr Int NTT<X>::rt;//INSERT ABOVE HEREsigned main(){Int P;cin>>P;vector<Int> as(P),bs(P);for(Int i=1;i<P;i++) cin>>as[i];for(Int i=1;i<P;i++) cin>>bs[i];random_device rd;mt19937 mt(rd());uniform_int_distribution<Int> ud(1,P-1);Int rt=ud(mt);while(order(rt,P)!=P-1) rt=ud(mt);vector<Int> rev(P);{Int res=1;for(Int i=0;i<P;i++){rev[res]=i;res=res*rt%P;}}vector<Int> A(P),B(P);for(Int i=1;i<P;i++){A[rev[i]]=as[i];B[rev[i]]=bs[i];}NTT<2> ntt;using M = decltype(ntt)::M;auto C=ntt.multiply(A,B);vector<M> cs(P);for(Int i=0;i<(Int)C.size();i++)cs[mod_pow(rt,i,P)]+=C[i];for(Int i=1;i<P;i++){if(i>1) cout<<" ";cout<<cs[i];}cout<<endl;return 0;}