文件详细信息

下载本文件

本文件的大小为 3236 字节。

#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;
const int maxn=1<<20;
const ll P=998244353;
inline void qmod(int&x){
	x=x+((x>>31)&int(P));
}
inline void qmod(ll&x){
	x=x+((x>>63)&P);
}
template<typename T>
void swap(T&a,T&b){
	const T temp=a;
	a=b;
	b=temp;
}
ll qpow(ll a,int x=P-2){
	ll answer=1;
	while(x){
		if(x&1)answer=answer*a%P;
		a=a*a%P;
		x>>=1;
	}
	return answer;
}
inline int get_n(const int deg){
	int n=1;
	while(n<=deg)n<<=1;
	return n;
}
const ll PR=3,invPR=qpow(PR);
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);
		}
		const int operator[](const int x)const{
			return tr[x];
		}
};
Transform<maxn<<1>tr;
template<typename T_store,typename T_calc>
struct Poly{
	private:
		std::vector<T_store>v;
	public:
		const auto operator[](const T_store x)const{
			return v[x];
		}
		const int deg(){
			return 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){
			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);
				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);
						qmod(v[l]+=temp-P);
						buf=buf*tPR%P;
					}
				}
			}
		}
		friend Poly<T_store,T_calc>operator*(Poly<T_store,T_calc>&F,const T_calc G){
			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>operator*(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G){
			const int len=F.deg()+G.deg(),n=get_n(len);
			F.ntt(true,n);
			G.ntt(true,n);
			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);
			H.set_deg(len);
			return H*qpow(n);
		}
};
Poly<int,ll>F,G,H;
int n,m;
int main(){
	read(n),read(m);
	F.init(n),G.init(m);
	H=F*G;
	H.output();
	return 0;
}