文件详细信息

下载本文件

本文件的大小为 4428 字节。

#include<cstdio>
#include<vector>
namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt=0;
		if(a<0)pc('-'),a=-a;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::write;
typedef long long ll;
typedef __int128 lll;
const int maxn=1<<20;
inline void qmod(int&x,const int P){
	x=x+((x>>31)&P);
}
inline void qmod(ll&x,const ll P){
	x=x+((x>>63)&P);
}
template<typename T>
void swap(T&a,T&b){
	const T temp=a;
	a=b;
	b=temp;
}
template<typename T>
T qpow(T a,T x,const T P){
	T answer=1;
	while(x){
		if(x&1)answer=answer*a%P;
		a=a*a%P;
		x>>=1;
	}
	return answer;
}
template<typename T>
void exgcd(T a,T b,T&x,T&y){
	if(!b)x=1,y=0;
	else exgcd(b,a%b,y,x),y-=(a/b)*x;
}
inline int get_n(const int deg){
	int n=1;
	while(n<=deg)n<<=1;
	return n;
}
template<const int size>
struct Transform{
	private:
		int tr[size],size_now;
	public:
		void init(const int n){
			if(size_now==n)return;
			size_now=n;
			for(int i=0;i<n;i++)tr[i]=(tr[i>>1]>>1)|((i&1)?(n>>1):0);
		}
		int operator[](const int x)const{
			return tr[x];
		}
};
Transform<maxn<<1>tr;
template<typename T>
struct Numbers{
	T P,PR,invPR,M,x,y;
};
Numbers<lll>num[3];
lll prod_P=1;
void initNumbers(){
	num[0].P=469762049,num[1].P=998244353,num[2].P=1004535809;
	for(int i=0;i<3;i++){
		prod_P*=num[i].P;
		num[i].invPR=qpow(num[i].PR=3,num[i].P-2,num[i].P);
	}
	for(int i=0;i<3;i++){
		num[i].M=prod_P/num[i].P;
		exgcd(num[i].M,num[i].P,num[i].x,num[i].y);
		num[i].x=(num[i].x%num[i].P+num[i].P)%num[i].P;
	}
}
template<typename T_store,typename T_calc>
struct Poly{
	private:
		std::vector<T_store>v;
	public:
		int&operator[](const T_store x){
			return v[x];
		}
		int deg(){
			return(int)v.size()-1;
		}
		void set_deg(const int n){
			v.resize(n+1);
		}
		void init(const int n){
			v.resize(n+1);
			for(int i=0;i<=n;i++)read(v[i]);
		}
		void output(){
			const int d=deg();
			for(int i=0;i<=d;i++)write(v[i]),pc(i!=d?' ':'\n');
		}
		void ntt(const bool type,const int n,const T_calc P,const T_calc PR,const T_calc invPR){
			tr.init(n);
			v.resize(n);
			for(int i=0;i<n;i++)
				if(i<tr[i])
					swap(v[i],v[tr[i]]);
			for(int p=2;p<=n;p<<=1){
				const int len=p>>1;
				const T_calc tPR=qpow(type?PR:invPR,(P-1)/p,P);
				for(int k=0;k<n;k+=p){
					T_calc buf=1;
					for(int l=k;l<k+len;l++){
						const T_calc temp=buf*v[l+len]%P;
						qmod(v[l+len]=v[l]-temp,P);
						qmod(v[l]+=temp-P,P);
						buf=buf*tPR%P;
					}
				}
			}
		}
		friend Poly<T_store,T_calc>poly_multiply(Poly<T_store,T_calc>&F,const T_calc G,const T_calc P){
			Poly H;
			H.v.resize(F.v.size());
			for(int i=0;i<(int)F.v.size();i++)H.v[i]=F.v[i]*G%P;
			return H;
		}
		friend Poly<T_store,T_calc>poly_multiply_directly(Poly<T_store,T_calc>F,Poly<T_store,T_calc>G,const T_calc P,const T_calc PR,const T_calc invPR){
			const int len=F.deg()+G.deg(),n=get_n(len);
			F.ntt(true,n,P,PR,invPR);
			G.ntt(true,n,P,PR,invPR);
			Poly<T_store,T_calc>H;
			H.v.resize(n);
			for(int i=0;i<n;i++)H.v[i]=(T_calc)F.v[i]*G.v[i]%P;
			H.ntt(false,n,P,PR,invPR);
			H.set_deg(len);
			return poly_multiply(H,qpow((ll)n,P-2,P),P);
		}
		friend Poly<T_store,T_calc>poly_multiply(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G,const T_calc P){
			const int n=F.deg()+G.deg();
			Poly<T_store,T_calc>H[3],ans;
			for(int i=0;i<3;i++)H[i]=poly_multiply_directly(F,G,num[i].P,num[i].PR,num[i].invPR);
			ans.set_deg(n);
			lll val;
			for(int j=0;j<=n;j++){
				val=0;
				for(int i=0;i<3;i++)val+=H[i][j]*num[i].M*num[i].x;
				ans[j]=val%prod_P%P;
			}
			return ans;
		}
};
Poly<int,ll>F,G,H;
int n,m,p;
int main(){
	initNumbers();
	read(n),read(m),read(p);
	F.init(n),G.init(m);
	H=poly_multiply(F,G,p);
	H.output();
	return 0;
}