显示代码纯文本
#include <ctime>
#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <algorithm>
typedef int TYPE;
const int MAXN=262144+10;
inline TYPE input() {
static int c;static TYPE k;k=0;
do c=getchar(); while(c<'0'||c>'9');
do k=k*10+c-'0',c=getchar(); while(c>='0'&&c<='9');
return k;
}
inline TYPE print(const TYPE&k,const char&end=' ') {
return printf("%d%c",k,end);
}
inline TYPE print(const TYPE*a,const int&N,const char&step=' ',const char&end='\n') {
for(int i=0;i<N;printf("%d%c",a[i++],step));
return printf("%c",end);
}
namespace Number_Theory {
const TYPE mod=998244353;
const TYPE god=3;
TYPE pow(TYPE a,TYPE b) {
TYPE ans=1;
for(ans=1;b;b>>=1ll,a=1ll*a*a%mod)
if(b&1)ans=1ll*ans*a%mod;
return ans;
}
void rotate(TYPE*a,int N) {
for(int i=1,j=0;i<N;++i) {
int k=N;
do {k>>=1;j^=k;}while(j<k);
if(i<j)std::swap(a[i],a[j]);
}
}
int SPFA=0;
void NTT(TYPE *a,int N,const int&is=1) {
SPFA+=N;
rotate(a,N);
for(int m=2;m<=N;m<<=1) {
const int mh=m>>1;
const TYPE wn=pow(god,is==1?mod-1-(mod-1)/m:(mod-1)/m);
for(int r=0;r<N;r+=m) {
TYPE w=1;
TYPE *b=a+r;
TYPE *c=a+r+mh;
for(int k=0;k<mh;++k) {
const unsigned int u=b[k];
const TYPE v=1ll*c[k]*w%mod;
b[k]=(u+v+mod)%mod;
c[k]=(u-v+mod)%mod;
w=1ll*w*wn%mod;
}
}
}
if(is<0) {
const TYPE inv=pow(N,mod-2);
for(int i=0;i<N;++i)
a[i]=1ll*a[i]*inv%mod;
}
}
//calc 1/a(x)
//
//
// g(x)*f(x) = 1 (mod x^n)
// g(x)*f(x)-1 = 0 (mod x^n)
// (g(x)*f(x)-1)^2 = 0 (mod x^2n)
// g^2(x)f^2(x)-2g(x)f(x)+1 = 0 (mod x^2n)
// 2g(x)f(x)-g^2(x)f^2(x) = 1 (mod x^2n)
// (2g(x)-g^2(x)*f(x))*f(x) = 1 (mod x^2n)
//
// new g(x) = 2g(x)-g^2(x)*f(x)
//
void inv(TYPE *a,TYPE*b,int N) {
static TYPE c[MAXN];
if(N==1) {
b[0]=pow(a[0],mod-2);
return ;
}inv(a,b,N>>1);
const int mh=N<<1;
memcpy(c,a,sizeof(TYPE)*N);
memset(c+N,0,sizeof(TYPE)*N);
//print(mh);
//printf("\n>>>");print(b,mh);
//printf(">>>");print(c,mh);
NTT(b,mh,1);NTT(c,mh,1);
for(int i=0;i<mh;++i) {
b[i]=1ll*(2ll-1ll*b[i]*c[i]%mod+mod)%mod*b[i]%mod;
}//print(N);print(b,N);
NTT(b,mh,-1);
memset(b+N,0,sizeof(TYPE)*N);
//print(N);print(b,N);
}
//calc sqrt(a(x))
//
//
// g^2(x) = f(x) (mod x^n)
// g^2(x)-f(x) = 0 (mod x^n)
// (g^2(x)-f(x))^2=0 (mod x^2n)
// (g^2(x)+f(x))^2=4g^2(x)f(x) (mod x^2n)
//
// g^2(x)+f(x)
// (---------------)^2 = f(x) (mod x^2n)
// 2g(x)
//
// (g(x)/2+f(x)*g-1(x)/2)^2 = f(x) (mod x^2n)
//
// new g(x)= g(x)/2+f(x)*g-1(x)/2
//
void Sqrt(TYPE *a,TYPE *b,int N) {
static TYPE c[MAXN],t[MAXN];
if(N==1) {
b[0]=sqrt(a[0]);
return ;
}
Sqrt(a,b,N>>1);
const TYPE inv2=pow(2,mod-2);
const int mh=N<<1;
memcpy(t,a,sizeof(TYPE)*N);
memset(c,0,sizeof(TYPE)*N);
inv(b,c,N);
NTT(t,mh,1);NTT(b,mh,1);NTT(c,mh,1);
for(int i=0;i<mh;++i) {
b[i]=(1ll*inv2*b[i]%mod+1ll*t[i]*c[i]%mod*inv2%mod)%mod;
}NTT(b,mh,-1);
memset(b+N,0,sizeof(TYPE)*N);//printf("%d 2333:\n",N);
}
//calc a(x)+=1
TYPE*self_add(TYPE *a,TYPE i) {(++a[i])%=mod;return a;}
//calc f'a(x) dx
TYPE* sigma(TYPE *a,TYPE *b,int N) {
for(int i=1;i<=N;++i) {
b[i]=1ll*a[i-1]*pow(i,mod-2)%mod;
}b[0]=0;
//print(b,N);
return b;
}
//calc a'(x)
TYPE* omiga(TYPE*a,TYPE*b,int N) {
for(int i=1;i<N;++i) {
b[i-1]=1ll*a[i]*i%mod;
}b[N-1]=0;
return b;
}
//calc ln a(x)
//
//
// b(x) = ln a(x)
// a'(x)
// b'(x) = ----------
// a(x)
//
// b(x) = f b'(x)
//
TYPE ln(TYPE *a,TYPE *b,int N) {
static TYPE oa[MAXN],ia[MAXN];
const int mh=N<<1;
memset(oa,0,sizeof(TYPE)*mh);
memset(ia,0,sizeof(TYPE)*mh);
omiga(a,oa,N);inv(a,ia,N);
NTT(oa,mh,1);NTT(ia,mh,1);
for(int i=0;i<mh;++i) {
oa[i]=1ll*oa[i]*ia[i]%mod;
}NTT(oa,mh,-1);
//printf("233333333333333333\n");
sigma(oa,b,N);
memset(b+N,0,sizeof(TYPE)*N);
}
//calc exp a(x)
//
// Newtown : x'=x-f(x)/f'(x)
//
void exp(TYPE *a,TYPE *b,int N) {
static TYPE c[MAXN];
if(N==1) {b[0]=1;return ;}
exp(a,b,N>>1);
const int mh=N<<1;
memset(c,0,sizeof(TYPE)*mh);
ln(b,c,N);
for(int i=0;i<N;++i) {
c[i]=((i==0)+a[i]-c[i]+mod)%mod;
}NTT(c,mh,1);NTT(b,mh,1);
for(int i=0;i<mh;++i){
b[i]=1ll*b[i]*c[i]%mod;
}NTT(b,mh,-1);
memset(b+N,0,sizeof(TYPE)*N);
}
// clac a^k(x)
// a^k(x)=exp(k*ln(a(x)))
//
void pow(TYPE*a,int k,int N) {
static TYPE c[MAXN]={0};
ln(a,c,N);
for(int i=0;i<N;++i)
c[i]=1ll*c[i]*k%mod;
memset(a,0,sizeof(TYPE)*N<<1);
exp(c,a,N);//print(a,N);
}
}
TYPE a[MAXN],b[MAXN];
int main() {
freopen("polynomial.in","r",stdin);
freopen("polynomial.out","w",stdout);
using namespace Number_Theory;
int M,K,N;
scanf("%d%d",&M,&K);
for(N=1;N<=M;N<<=1);
for(int i=0;i<M;a[i++]=input());
//NTT(a,N,1);NTT(a,N,-1);print(a,N);
Sqrt(a,b,N); memset(a,0,sizeof(TYPE)*N<<1);//print(b,N);
inv(b,a,N); memset(b,0,sizeof(TYPE)*N<<1);
sigma(a,b,N); memset(a,0,sizeof(TYPE)*N<<1);
exp(b,a,N); memset(b,0,sizeof(TYPE)*N<<1);
inv(a,b,N); memset(a,0,sizeof(TYPE)*N<<1);
self_add(b,0);
ln(b,a,N); memset(b,0,sizeof(TYPE)*N<<1);
self_add(a,0);
pow(a,K,N); //print(a,N);
omiga(a,b,N); b[M-1]=0;
if(M==100000)printf("%d\n",SPFA);
for(int i=0;i<M;print(b[i++]));
//printf("\n%d",clock());
return 8==3;
}
YGOI_真神名曰驴蛋蛋