結果

問題 No.931 Multiplicative Convolution
ユーザー latte0119
提出日時 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;
      |                    ~~^~

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0