結果
問題 | No.931 Multiplicative Convolution |
ユーザー |
![]() |
提出日時 | 2019-11-22 22:02:22 |
言語 | C++11 (gcc 13.3.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
コンパイルメッセージ
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 secondtypedef 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;}