文件详细信息

下载本文件

本文件的大小为 3143 字节。

#include<algorithm>
#include<functional>
#include<iostream>
#include<vector>
using std::cin;
using std::cout;
typedef long long ll;
template<const int P>
class mod_int{
	using Z=mod_int;
	private:
		static int mod(const int x){
			return x<0?x+P:x;
		}
	public:
		int x;
		int val()const{
			return x;
		}
		mod_int():x(0){}
		template<typename T>
		mod_int(const T&_x):x(_x>=0&&_x<P?static_cast<int>(_x):mod(static_cast<int>(_x%P))){}
		Z pow(ll k)const{
			Z res=1,t=*this;
			while(k){
				if(k&1)res*=t;
				if(k>>=1)t*=t;
			}
			return res;
		}
		Z inv()const{
			return pow(P-2);
		}
		Z&operator+=(const Z&rhs){
			(x+=rhs.x)>=P&&(x-=P);
			return*this;
		}
		Z&operator-=(const Z&rhs){
			(x-=rhs.x)<0&&(x+=P);
			return*this;
		}
		Z&operator*=(const Z&rhs){
			x=(ll)x*rhs.x%P;
			return*this;
		}
		#define setO(T,o)\
		friend T operator o(const Z&lhs,const Z&rhs){\
			Z res=lhs;\
			return res o##=rhs;\
		}
		setO(Z,+);
		setO(Z,-);
		setO(Z,*);
		#undef setO
};
const int P=998244353,R=3;
using Z=mod_int<P>;
namespace Poly_space{
	std::vector<int>rev;
	std::vector<Z>roots{0,1};
	void init_rev(const int n){
		if((int)rev.size()!=n)rev.resize(n);
		for(int i=0;i<n;i++)rev[i]=rev[i>>1]>>1|(i&1?n>>1:0);
	}
	void init_roots(const int n){
		if((int)roots.size()<n){
			int k=__builtin_ctz((int)roots.size());
			roots.resize(n);
			for(Z e;(1<<k)<n;k++){
				e=Z(3).pow((P-1)>>(k+1));
				for(int i=1<<(k-1);i<(1<<k);i++){
					roots[i<<1]=roots[i];
					roots[i<<1|1]=roots[i]*e;
				}
			}
		}
	}
	void dft(std::vector<Z>&A){
		const int n=A.size();
		init_rev(n);
		for(int i=0;i<n;i++)
			if(i<rev[i])
				std::swap(A[i],A[rev[i]]);
		init_roots(n);
		Z u,v;
		for(int k=1;k<n;k<<=1)
			for(int i=0;i<n;i+=k<<1)
				for(int j=0;j<k;j++){
					u=A[i+j],v=A[i+j+k]*roots[j+k];
					A[i+j]=u+v,A[i+j+k]=u-v;
				}
	}
	void idft(std::vector<Z>&A){
		const int n=A.size();
		std::reverse(A.begin()+1,A.end());
		dft(A);
		const Z coef=Z(n).inv();
		for(int i=0;i<n;i++)A[i]*=coef;
	}
	struct Poly{
		std::vector<Z>V;
		Poly(){}
		Poly(const std::vector<Z>&_V):V(_V){}
		Poly(const std::initializer_list<Z>&_V):V(_V){}
		int size()const{
			return(int)V.size();
		}
		void resize(const int n){
			V.resize(n);
		}
		Z operator[](const int k)const{
			return k>=0&&k<(int)V.size()?V[k]:Z(0);
		}
		void input(const int deg){
			V.resize(deg+1);
			for(int i=0;i<=deg;i++)cin>>V[i].x;
		}
		void output(const int deg){
			for(int i=0;i<=deg;i++)cout<<V[i].x<<(i!=deg?' ':'\n');
		}
		friend Poly mul(Poly A,Poly B,std::function<Z(Z,Z)>func){
			if(!A.size()||!B.size())return Poly();
			const int tot=A.size()+B.size()-1,sz=1<<(32-__builtin_clz(tot-1));
			A.resize(sz);
			dft(A.V);
			B.resize(sz);
			dft(B.V);
			for(int i=0;i<sz;i++)A.V[i]=func(A[i],B[i]);
			idft(A.V);
			return A;
		}
		friend Poly operator*(const Poly&A,const Poly&B){
			return mul(A,B,[](const Z a,const Z b){
				return a*b;
			});
		}
	};
}
using Poly_space::Poly;
void solve(){
	int n,m;
	Poly F,G;
	cin>>n>>m;
	F.input(n),G.input(m);
	(F*G).output(n+m);
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	solve();
	return 0;
}