文件详细信息
本文件的大小为 9696 字节。
#include<chrono>
#include<cstdio>
#include<random>
#include<functional>
#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 read_mod(T&num1,const T P1,T&num2,const T P2,bool&is_large){
int ch=gc();
num1=num2=0;
is_large=false;
while(ch<48||ch>57)ch=gc();
while(ch>=48&&ch<=57){
num1=(num1<<3)+(num1<<1)+(ch^48);
if(num1>=P1)num1%=P1,is_large=true;
num2=(num2<<3)+(num2<<1)+(ch^48);
if(num2>=P2)num2%=P2,is_large=true;
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--]);
}
void putstr(const char*str){
while(*str!='\0')pc(*(str++));
}
}
using IO::read;
using IO::read_mod;
using IO::write;
using IO::putstr;
std::mt19937_64 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
const int maxn=1<<18;
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),inv_2=qpow(2);
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;
}
ll solve(){
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 ll ans=qpow(CP{a,1},(p+1)>>1);
if((ans<<1)>p)return p-ans;
return ans;
}
}
struct Inverse{
int inv[maxn+1];
Inverse(){
inv[1]=1;
for(int i=2;i<=maxn;i++)inv[i]=ll(P-P/i)*inv[P%i]%P;
}
int operator[](const int x){
return inv[x];
}
}inv;
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);
}
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:
int operator[](const T_store x)const{
return v[x];
}
int deg(){
return(int)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){
Poly<T_store,T_calc>H;
int len1=F.deg(),len2=G.deg();
if(len1<len2){
H.set_deg(len2);
for(int i=0;i<=len1;i++)qmod(H.v[i]=F[i]-G[i]);
for(int i=len1+1;i<=len2;i++)qmod(H.v[i]=-G[i]);
}else{
H.set_deg(len1);
for(int i=0;i<=len2;i++)qmod(H.v[i]=F[i]-G[i]);
for(int i=len2+1;i<=len1;i++)H.v[i]=F[i];
}
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);
}
friend Poly<T_store,T_calc>poly_multiply(Poly<T_store,T_calc>F,Poly<T_store,T_calc>G,std::function<T_store(T_store,T_store)>func){
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]=func(F.v[i],G.v[i]);
H.ntt(false,n);
H.set_deg(len);
return H*qpow(n);
}
friend Poly<T_store,T_calc>poly_multiply_reference(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G,std::function<T_store(T_store,T_store)>func){
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]=func(F.v[i],G.v[i]);
H.ntt(false,n);
H.set_deg(len);
return H*qpow(n);
}
friend void poly_inverse(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G){
const int len=F.deg(),n=get_n(len);
F.v.resize(n<<1);
G.v.clear();
G.v.reserve(n<<1);
G.v.emplace_back(qpow(F[0]));
Poly<T_store,T_calc>A,B;
A.v.reserve(n<<1);
B.v.reserve(n<<1);
for(int l=1;l<=(len<<1);l<<=1){
const int lim=l<<1;
A.v.clear();
A.v.insert(A.v.begin(),F.v.begin(),F.v.begin()+l);
B.v.clear();
B.v.insert(B.v.begin(),G.v.begin(),G.v.begin()+l);
G=poly_multiply_reference(A,B,[](const T_store x,const T_store y){
return T_store((P+2-(T_calc)x*y%P)*y%P);
});
for(int i=l;i<lim;i++)G.v[i]=0;
}
F.set_deg(len);
G.set_deg(len);
}
friend void poly_sqrt(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G){
const int len=F.deg(),n=get_n(len);
F.v.resize(n<<1);
G.v.clear();
G.v.resize(n<<1);
QuadraticResidue::n=F[0],QuadraticResidue::p=P;
G.v[0]=QuadraticResidue::solve();
Poly<T_store,T_calc>A,B,invB;
A.v.reserve(n<<1);
B.v.reserve(n<<1);
invB.v.reserve(n<<1);
for(int l=1;l<=(len<<1);l<<=1){
const int lim=l<<1;
A.v.clear();
A.v.insert(A.v.begin(),F.v.begin(),F.v.begin()+l);
B.v.clear();
B.v.insert(B.v.begin(),G.v.begin(),G.v.begin()+l);
poly_inverse(B,invB);
A=poly_multiply_reference(A,invB,[](const T_store x,const T_store y){
return T_store((T_calc)x*y%P);
});
for(int i=0;i<l;i++)G.v[i]=T_calc(A[i]+B[i])*inv_2%P;
for(int i=l;i<lim;i++)G.v[i]=0;
}
F.set_deg(len);
G.set_deg(len);
}
friend void poly_derivation(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G){
const int n=F.deg();
G.set_deg(n);
for(int i=1;i<=n;i++)G.v[i-1]=(T_calc)F[i]*i%P;
G.v[n]=0;
}
friend void poly_integral(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G){
const int n=F.deg();
G.set_deg(n);
for(int i=1;i<=n;i++)G.v[i]=(T_calc)F[i-1]*inv[i]%P;
G.v[0]=0;
}
friend void poly_ln(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G){
Poly<T_store,T_calc>F_derivation,F_inv,G_derivation;
poly_derivation(F,F_derivation);
poly_inverse(F,F_inv);
G_derivation=poly_multiply(F_derivation,F_inv,[](const T_store x,const T_store y){
return T_store((T_calc)x*y%P);
});
G_derivation.set_deg(F.deg());
poly_integral(G_derivation,G);
}
friend void poly_exp(Poly<T_store,T_calc>&F,Poly<T_store,T_calc>&G){
const int len=F.deg(),n=get_n(len);
F.v.resize(n<<1);
G.v.clear();
G.v.reserve(n<<1);
G.v.emplace_back(1);
Poly<T_store,T_calc>A,B,C;
A.v.reserve(n<<1);
B.v.reserve(n<<1);
for(int l=1;l<=(len<<1);l<<=1){
const int lim=l<<1;
A.v.clear();
A.v.insert(A.v.begin(),F.v.begin(),F.v.begin()+l);
B.v.clear();
B.v.insert(B.v.begin(),G.v.begin(),G.v.begin()+l);
poly_ln(B,C);
C=A-C;
qmod(C.v[0]+=1-P);
G=poly_multiply_reference(B,C,[](const T_store x,const T_store y){
return T_store((T_calc)x*y%P);
});
for(int i=l;i<lim;i++)G.v[i]=0;
}
F.set_deg(len);
G.set_deg(len);
}
friend void poly_pow(Poly<T_store,T_calc>F,Poly<T_store,T_calc>&G,const int k1,const int k2,const bool is_large){
const int len=F.deg();
G.v.clear();
int first_none_zero=0;
while(first_none_zero<=len&&!F[first_none_zero])first_none_zero++;
if((ll)first_none_zero*k1>len||(first_none_zero&&is_large)){
G.v.resize(len+1,0);
return;
}
T_store inv_1=qpow(F.v[first_none_zero]),inv_2=qpow(F.v[first_none_zero],k2);
for(int i=first_none_zero;i<=len;i++)F.v[i-first_none_zero]=(T_calc)F.v[i]*inv_1%P;
Poly<T_store,T_calc>ln_F;
poly_ln(F,ln_F);
ln_F=ln_F*k1;
poly_exp(ln_F,G);
const int zero_cnt=first_none_zero*k1;
G.v.insert(G.v.begin(),zero_cnt,0);
G.set_deg(len);
for(int i=zero_cnt;i<=len;i++)G.v[i]=(T_calc)G.v[i]*inv_2%P;
}
};
Poly<int,ll>F,G;
int n;
ll k1,k2;
bool is_large;
int main(){
read(n),n--,read_mod(k1,P,k2,P-1,is_large);
F.init(n);
poly_pow(F,G,k1,k2,is_large);
G.output();
return 0;
}