結果

問題 No.931 Multiplicative Convolution
ユーザー latte0119latte0119
提出日時 2019-11-22 22:02:22
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 131 ms / 2,000 ms
コード長 4,222 bytes
コンパイル時間 1,261 ms
コンパイル使用メモリ 168,304 KB
実行使用メモリ 8,068 KB
最終ジャッジ日時 2024-04-19 11:26:34
合計ジャッジ時間 3,466 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 14 ms
5,376 KB
testcase_08 AC 130 ms
7,940 KB
testcase_09 AC 82 ms
7,956 KB
testcase_10 AC 125 ms
7,904 KB
testcase_11 AC 81 ms
7,688 KB
testcase_12 AC 80 ms
5,988 KB
testcase_13 AC 127 ms
7,820 KB
testcase_14 AC 131 ms
8,068 KB
testcase_15 AC 131 ms
7,816 KB
testcase_16 AC 127 ms
7,828 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;
      |                    ~~^~

ソースコード

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;
}
0