文件详细信息

下载本文件

本文件的大小为 7127 字节。

#include<algorithm>
#include<chrono>
#include<functional>
#include<iostream>
#include<random>
#include<vector>
std::mt19937_64 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
using std::cin;
using std::cout;
typedef long long ll;
namespace QuadraticResidue{
	ll n,p,a,w;
	struct CP{
		ll x,y;
	};
	CP operator*(CP x,CP y){
		return CP{(x.x*y.x+x.y*y.y%p*w)%p,(x.x*y.y+x.y*y.x)%p};
	}
	ll qpow(ll a,ll x){
		ll ans=1;
		while(x){
			if(x&1)ans=ans*a%p;
			a=a*a%p;
			x>>=1;
		}
		return ans;
	}
	ll qpow(CP a,ll x){
		CP ans=CP{1,0};
		while(x){
			if(x&1)ans=ans*a;
			a=a*a;
			x>>=1;
		}
		return ans.x;
	}
	int solve(const int _n,const int _p){
		n=_n,p=_p;
		n%=p;
		if(n==0)return 0;
		if(p==2)return n;
		if(qpow(n,p>>1)==p-1)return-1;
		do a=rnd()%p,w=(p+a*a-n)%p;
		while(qpow(w,p>>1)!=p-1);
		const int ans=qpow(CP{a,1},(p+1)>>1);
		return std::min(ans,_p-ans);
	}
}
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 maxn=100000,P=998244353,R=3;
using Z=mod_int<P>;
std::vector<Z>inv{0,1};
void init_inv(const int n){
	const int m=(int)inv.size()-1;
	if(m<n){
		inv.resize(n+1);
		for(int i=m+1;i<=n;i++)inv[i]=Z(P-P/i)*inv[P%i];
	}
	
}
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;
		}
		Poly mul_val(const Z val){
			std::vector<Z>_V=V;
			for(Z&v:_V)v*=val;
			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 mul(Poly A,Poly B,Poly C,std::function<Z(Z,Z,Z)>func){
			if(!A.size()||!B.size()||!C.size())return Poly();
			const int tot=A.size()+B.size()+C.size()-2,sz=1<<(32-__builtin_clz(tot-1));
			A.resize(sz);
			dft(A.V);
			B.resize(sz);
			dft(B.V);
			C.resize(sz);
			dft(C.V);
			for(int i=0;i<sz;i++)A.V[i]=func(A[i],B[i],C[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);
		}
		Poly derivative(){
			const int n=size();
			if(!n)return Poly();
			Poly X;
			X.resize(n-1);
			for(int i=1;i<n;i++)X.V[i-1]=V[i]*i;
			return X;
		}
		Poly integral(){
			const int n=size();
			Poly X;
			X.resize(n+1);
			init_inv(n);
			for(int i=1;i<=n;i++)X.V[i]=V[i-1]*::inv[i];
			return X;
		}
		Poly log(){
			const int n=size();
			return(derivative()*inv(n)).modxk(n-1).integral();
		}
		Poly exp(){
			const int n=size();
			Poly G{1},logG;
			int k=1;
			while(k<n){
				k<<=1;
				G.resize(k);
				logG=G.log();
				G=mul(modxk(k),G,logG,[&](const Z F,const Z G,const Z logG){
					return G*(1+F-logG);
				}).modxk(k);
			}
			return G.modxk(n);
		}
		Poly pow(const int k,const int k1,const bool is_large){//k mod p; k mod (p-1)
			const int n=size();
			int zero=0;
			while(zero<n&&!V[zero].x)zero++;
			Poly F;
			if(zero&&(is_large||(ll)zero*k>=n)){
				F.resize(n);
				return F;
			}
			const int zero_k=zero*k;
			F=this->divxk(zero).modxk(n-zero_k);
			const Z v0=F[0];
			F=F.mul_val(v0.inv());
			F=F.log().mul_val(k).exp();
			F=F.mul_val(v0.pow(k1));
			F=F.mulxk(zero_k);
			return F;
		}
	};
}
using Poly_space::Poly;
bool input_mod(int&x0,const int P0,int&x1,const int P1){
	x0=x1=0;
	bool is_large=0;
	char ch;
	do ch=cin.get();
	while(ch<'0'||ch>'9');
	do{
		x0=(x0*10ll+(ch-'0'))%P0;
		x1=(x1*10ll+(ch-'0'))%P1;
		if(x0>maxn)is_large=true;
		ch=cin.get();
	}while(ch>='0'&&ch<='9');
	return is_large;
}
void solve(){
	int n,k,k1;
	Poly F,G;
	cin>>n;
	const bool is_large=input_mod(k,P,k1,P-1);
	F.input(n-1);
	G=F.pow(k,k1,is_large);
	G.output(n-1);
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	solve();
	return 0;
}