文件详细信息

下载本文件

本文件的大小为 6034 字节。

#include<algorithm>
#include<functional>
#include<iostream>
#include<vector>
using std::cin;
using std::cout;
typedef long long ll;
typedef __int128 lll;
struct Number{
	int P,PR;
	ll M,x;
};
constexpr Number N[3]={{469762049,3,1002772198720536577ll,354521948ll},{998244353,3,471892799929712641ll,850356001ll},{1004535809,3,468937312667959297ll,395249030ll}};
constexpr lll prod_P=(lll)N[0].P*N[1].P*N[2].P;
int _P[4]={469762049,998244353,1004535809,-1};
int merge(const int v[3],const int P){
	lll val=0;
	for(int i=0;i<3;i++)val+=(lll)v[i]*N[i].M*N[i].x;
	return val%prod_P%P;
}
template<const int Pid>
class mod_int{
	#define P _P[Pid]
	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
	#undef P
};
template<const int Pid>
struct Poly_space{
	#define P _P[Pid]
	#define R N[Pid].PR
	using Z=mod_int<Pid>;
	static std::vector<int>rev;
	static std::vector<Z>roots;
	static 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);
	}
	static 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(R).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;
				}
			}
		}
	}
	static 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;
				}
	}
	static 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){}
		template<const int TargetPid>
		typename Poly_space<TargetPid>::Poly convert_to()const{
			typename Poly_space<TargetPid>::Poly result;
			result.V.reserve(V.size());
			std::transform(V.begin(),V.end(),std::back_inserter(result.V),[](const Z&v){
				return mod_int<TargetPid>(v.x);
			});
			return result;
		}
		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 modxk(const int k)const{
			std::vector<Z>_V(k);
			std::copy(V.begin(),V.begin()+std::min(k,size()),_V.begin());
			return _V;
		}
		Poly mul_val(const Z val){
			Poly _V;
			const int n=V.size();
			_V.resize(n);
			for(int i=0;i<n;i++)_V.V[i]=V[i]*val;
			return _V;
		}
		friend Poly operator-(const Poly&A,const Poly&B){
			Poly C;
			const int n=std::max(A.size(),B.size());
			C.resize(n);
			for(int i=0;i<n;i++)C.V[i]=A[i]-B[i];
			return C;
		}
		#define func0(x,y) ((x)*(y))
		#define func1(x,y) ((y)*(2-(x)*(y)))
		#define func(x,y) ((func_id==0)?(func0(x,y)):(func1(x,y)))
		friend Poly mul(Poly A,Poly B,const int func_id){
			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);
			if(Pid<3){
				Poly_space<Pid>::dft(A.V);
				B.resize(sz);
				Poly_space<Pid>::dft(B.V);
				for(int i=0;i<sz;i++)A.V[i]=func(A[i],B[i]);
				Poly_space<Pid>::idft(A.V);
				A.resize(tot);
			}else{
				auto A0=A.template convert_to<0>();
				{
					auto B0=B.template convert_to<0>();
					A0=mul(A0,B0,func_id);
				}
				auto A1=A.template convert_to<1>();
				{
					auto B1=B.template convert_to<1>();
					A1=mul(A1,B1,func_id);
				}
				auto A2=A.template convert_to<2>();
				{
					auto B2=B.template convert_to<2>();
					A2=mul(A2,B2,func_id);
				}
				for(int i=0,v[3];i<sz;i++){
					v[0]=A0[i].x,v[1]=A1[i].x,v[2]=A2[i].x;
					A.V[i]=merge(v,P);
				}
			}
			return A;
		}
		#undef func0
		#undef func1
		#undef func
		friend Poly operator*(const Poly&A,const Poly&B){
			return mul(A,B,0);
		}
		Poly inv(const int n){
			Poly X{V[0].inv()},Y;
			int k=1;
			while(k<n){
				k<<=1;
				X=(X.mul_val(2)-modxk(k)*(X*X)).modxk(k);
			}
			return X.modxk(n);
		}
	};
	#undef P
	#undef R
};
template<const int Pid>
std::vector<int>Poly_space<Pid>::rev;
template<const int Pid>
std::vector<mod_int<Pid>>Poly_space<Pid>::roots={mod_int<Pid>(0),mod_int<Pid>(1)};
void solve(){
	int n;
	Poly_space<3>::Poly F,G;
	cin>>n;
	_P[3]=1000000007;
	F.input(n-1);
	G=F.inv(n);
	G.output(n-1);
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	solve();
	return 0;
}