文件详细信息

下载本文件

本文件的大小为 2530 字节。

#include<cstdio>
#include<cstring>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[40],cnt;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
template<typename T>
inline void my_swap(T&a,T&b){
	const T temp=a;
	a=b;
	b=temp;
}
typedef long long ll;
typedef __int128 lll;
const int maxn=1<<18;
lll total_P;
ll qpow(ll a,ll x,ll P){
	a%=P;
	ll ans=1;
	while(x){
		if(x&1)ans=ans*a%P;
		a=a*a%P;
		x>>=1;
	}
	return ans;
}
int n,m,_n,_m,tr[maxn];
int f[maxn],g[maxn],_g[maxn],buf[maxn];
struct NTT{
	int P,G,invG;
	int f[maxn],*g;
	lll M,x,y;
	inline void qmod(int&a){
		a=(P&(a>>31))+a;
	}
	void ntt(int*f,int mode){
		for(int i=0;i<n;i++)
			if(tr[i]<i)
				my_swap(f[tr[i]],f[i]);
		for(int p=2;p<=n;p<<=1){
			const int len=p>>1,tG=qpow((mode==1)?G:invG,(P-1)/p,P);
			buf[0]=1;
			for(int l=1;l<len;l++)buf[l]=(ll)buf[l-1]*tG%P;
			for(int k=0;k<n;k+=p){
				for(int l=k;l<k+len;l++){
					const int tmp=(ll)buf[l-k]*f[l+len]%P;
					qmod(f[l+len]=f[l]-tmp);
					qmod(f[l]=f[l]+tmp-P);
				}
			}
		}
	}
}data[3];
lll mul=1;
void exgcd(lll a,lll b,lll&x,lll&y){
	if(!b)x=1,y=0;
	else exgcd(b,a%b,y,x),y-=(a/b)*x;
}
int main(){
	data[0].P=469762049,data[1].P=998244353,data[2].P=1004535809;
	for(int i=0;i<3;i++){
		mul*=data[i].P;
		data[i].invG=qpow(data[i].G=3,data[i].P-2,data[i].P);
		data[i].g=_g;
	}
	read(n),read(m),read(total_P);
	_n=n,_m=m;
	for(int i=0;i<=n;i++)read(f[i]);
	for(int i=0;i<=m;i++)read(g[i]);
	for(m+=n,n=1;n<=m;n<<=1);
	for(int i=0;i<n;i++)tr[i]=(tr[i>>1]>>1)+((i&1)?(n>>1):0);
	for(int i=0;i<3;i++){
		data[i].M=mul/data[i].P;
		for(int j=0;j<=_n;j++)data[i].f[j]=f[j]%data[i].P;
		for(int j=0;j<=_m;j++)data[i].g[j]=g[j]%data[i].P;
		memset(data[i].g+_m+1,0,sizeof(int)*(n-_m-1));
		data[i].ntt(data[i].f,1),data[i].ntt(data[i].g,1);
		for(int j=0;j<n;j++)data[i].f[j]=(ll)data[i].f[j]*data[i].g[j]%data[i].P;
		data[i].ntt(data[i].f,-1);
		ll invn=qpow(n,data[i].P-2,data[i].P);
		for(int j=0;j<=m;j++)data[i].f[j]=data[i].f[j]*invn%data[i].P;
	}
	lll answer;
	for(int i=0;i<3;i++){
		exgcd(data[i].M,data[i].P,data[i].x,data[i].y);
		data[i].x=(data[i].x%data[i].P+data[i].P)%data[i].P;
	}
	for(int j=0;j<=m;j++){
		answer=0;
		for(int i=0;i<3;i++)answer+=data[i].f[j]*data[i].M*data[i].x;
		write(answer%mul%total_P),putchar(j!=m?' ':'\n');
	}
	return 0;
}