文件详细信息

下载本文件

本文件的大小为 4234 字节。

#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))){}
		bool operator==(const Z&rhs){
			return x==rhs.x;
		}
		bool operator!=(const Z&rhs){
			return x!=rhs.x;
		}
		Z operator-()const{
			return Z(x?P-x:0);
		}
		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&operator++(){
			x<P-1?++x:x=0;
			return*this;
		}
		Z&operator--(){
			x?--x:x=P-1;
			return*this;
		}
		Z&operator++(int){
			Z ret=*this;
			x<P-1?++x:x=0;
			return ret;
		}
		Z&operator--(int){
			Z ret=*this;
			x?--x:x=P-1;
			return ret;
		}
		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;
		}
		Z&operator/=(const Z&rhs){
			x=(ll)x*rhs.inv().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,*);
		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');
		}
		Poly mulxk(const int k)const{
			if(!size())return Poly();
			std::vector<Z>_V=V;
			_V.insert(_V.begin(),k,0);
			return Poly(_V);
		}
		Poly divxk(const int k)const{
			if(size()<=k)return Poly();
			return Poly(std::vector<Z>(V.begin()+k,V.end()));
		}
		Poly modxk(const int k)const{
			std::vector<Z>_V(k);
			std::copy(V.begin(),V.begin()+std::min(k,size()),_V.begin());
			return _V;
		}
		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;
			});
		}
		Poly inv(const int n){
			Poly X{V[0].inv()};
			int k=1;
			while(k<n){
				k<<=1;
				X=mul(modxk(k),X,[](const Z F,const Z G){
					return G*(2-F*G);
				}).modxk(k);
			}
			return X.modxk(n);
		}
	};
}
using Poly_space::Poly;
void solve(){
	int n;
	Poly F;
	cin>>n;
	F.input(n-1);
	F.inv(n).output(n-1);
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	solve();
	return 0;
}