結果
問題 | No.931 Multiplicative Convolution |
ユーザー | latte0119 |
提出日時 | 2019-11-22 22:02:22 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 145 ms / 2,000 ms |
コード長 | 4,222 bytes |
コンパイル時間 | 1,391 ms |
コンパイル使用メモリ | 169,700 KB |
実行使用メモリ | 8,064 KB |
最終ジャッジ日時 | 2024-10-11 03:39:42 |
合計ジャッジ時間 | 3,658 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 1 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 1 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,816 KB |
testcase_06 | AC | 3 ms
6,820 KB |
testcase_07 | AC | 16 ms
6,816 KB |
testcase_08 | AC | 145 ms
7,948 KB |
testcase_09 | AC | 89 ms
7,824 KB |
testcase_10 | AC | 136 ms
7,776 KB |
testcase_11 | AC | 90 ms
7,812 KB |
testcase_12 | AC | 86 ms
6,816 KB |
testcase_13 | AC | 139 ms
7,952 KB |
testcase_14 | AC | 140 ms
7,940 KB |
testcase_15 | AC | 144 ms
8,064 KB |
testcase_16 | AC | 141 ms
7,832 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:185:22: warning: ‘g’ may be used uninitialized in this function [-Wmaybe-uninitialized] 185 | gg=gg*g%P; | ~~^~
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define eb emplace_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} template<class A,class B> ostream& operator<<(ostream& ost,const pair<A,B>&p){ ost<<"{"<<p.first<<","<<p.second<<"}"; return ost; } template<class T> ostream& operator<<(ostream& ost,const vector<T>&v){ ost<<"{"; for(int i=0;i<v.size();i++){ if(i)ost<<","; ost<<v[i]; } ost<<"}"; return ost; } template<uint32_t mod> struct ModInt{ uint32_t a; ModInt& s(uint32_t vv){ a=vv<mod?vv:vv-mod; return *this; } ModInt(int64_t x=0){s(x%mod+mod);} ModInt& operator+=(const ModInt &x){return s(a+x.a);} ModInt& operator-=(const ModInt &x){return s(a+mod-x.a);} ModInt& operator*=(const ModInt &x){ a=uint64_t(a)*x.a%mod; return *this; } ModInt& operator/=(const ModInt &x){ *this*=x.inv(); return *this; } ModInt operator+(const ModInt &x)const{return ModInt(*this)+=x;} ModInt operator-(const ModInt &x)const{return ModInt(*this)-=x;} ModInt operator*(const ModInt &x)const{return ModInt(*this)*=x;} ModInt operator/(const ModInt &x)const{return ModInt(*this)/=x;} bool operator==(const ModInt &x)const{return a==x.a;} bool operator!=(const ModInt &x)const{return a!=x.a;} bool operator<(const ModInt &x)const{return a<x.a;} ModInt operator-()const{return ModInt()-*this;} ModInt pow(int64_t n)const{ ModInt res(1),x(*this); while(n){ if(n&1)res*=x; x*=x; n>>=1; } return res; } ModInt inv()const{return pow(mod-2);} }; template<uint32_t mod> istream& operator>>(istream& in,const ModInt<mod>& a){ return (in>>a.a); } template<uint32_t mod> ostream& operator<<(ostream& out,const ModInt<mod>& a){ return (out<<a.a); } //using mint=ModInt<1000000007>; using mint=ModInt<998244353>; template<class Mint,int32_t root> struct NumberTheoreticTransform{ static void ntt(vector<Mint>&f){ int n=f.size(); int s=__lg(n); for(int i=0,j=1;j<n-1;j++){ for(int k=n>>1;k>(i^=k);k>>=1); if(i>j)swap(f[i],f[j]); } for(int m=1;m<=s;m++){ Mint wr=Mint(root).pow(Mint(-1).a>>m); for(int i=0;i<n;i+=1<<m){ Mint w=1; for(int j=0;j<1<<m-1;j++){ Mint f0=f[i+j],f1=w*f[i+j+(1<<m-1)]; f[i+j]=f0+f1; f[i+j+(1<<m-1)]=f0-f1; w*=wr; } } } } static void intt(vector<Mint>&f){ reverse(f.begin()+1,f.end()); ntt(f); Mint in=Mint(f.size()).inv(); for(int i=0;i<f.size();i++)f[i]*=in; } static vector<Mint>convolute(const vector<Mint>&A,const vector<Mint>&B){ int n=1<<__lg(A.size()+B.size()-2)+1; vector<Mint>a=A,b=B; a.resize(n);b.resize(n); ntt(a); ntt(b); for(int i=0;i<n;i++)a[i]*=b[i]; intt(a); a.resize(A.size()+B.size()-1); return a; } }; using NTT=NumberTheoreticTransform<mint,3>; int mpow(int n,int m,int P){ int ret=1; while(m){ if(m&1)ret=ret*n%P; n=n*n%P; m>>=1; } return ret; } signed main(){ int P;cin>>P; vint A(P),B(P); for(int i=1;i<P;i++)cin>>A[i]; for(int i=1;i<P;i++)cin>>B[i]; if(P==2){ cout<<A[1]*B[1]%998244353<<endl; return 0; } vint lis; for(int i=2;i<P-1;i++)if((P-1)%i==0)lis.pb(i); int g; for(int i=2;i<P;i++){ bool ok=true; for(auto &d:lis){ if(mpow(i,d,P)==1){ ok=false; break; } } if(ok){ g=i; break; } } vector<mint>X(P-1),Y(P-1); int gg=1; for(int i=0;i<P-1;i++){ X[i]=A[gg]; Y[i]=B[gg]; gg=gg*g%P; } auto Z=NTT::convolute(X,Y); for(int i=P-1;i<Z.size();i++)Z[i%(P-1)]+=Z[i]; gg=1; vint ans(P); for(int i=0;i<P-1;i++){ ans[gg]=Z[i].a; gg=gg*g%P; } for(int i=1;i<P;i++){ if(i>1)printf(" "); printf("%lld",ans[i]); } puts(""); return 0; }