跑的很慢。因为没有用什么看不懂的东西。
刚刚写完比较基本的东西，持续更新。
要是内存爆就把多点求值和快速插值干掉。
示例代码为挑战多项式，2077ms。（多项式全家桶 2077）
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
const int mod=998244353;
#define add(x,y) (x+y>=mod?x+y-mod:x+y)
#define sub(x,y) (x-y<0?x-y+mod:x-y)
namespace IO{
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(10ll*x+ch-'0')%mod,ch=getchar();
return x;
}
void print(int x){
if(x>9)print(x/10);
putchar(x%10+'0');
}
}
inline int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
namespace Math{
int jc[300010],inv[300010],Inv[300010];
inline int C(int n,int m){
if(n<m||m<0)return 0;
return 1ll*jc[n]*Inv[m]%mod*Inv[n-m]%mod;
}
namespace Cipolla{
int n,I;
struct cp{
int r,i;
inline cp(int a=0,int b=0){r=a;i=b;}
inline bool operator==(const cp &s)const{return r==s.r&&i==s.i;}
inline cp operator+(const cp &s)const{return cp{(r+s.r)%mod,(i+s.i)%mod};}
inline cp operator-(const cp &s)const{return cp{(r-s.r+mod)%mod,(i-s.i+mod)%mod};}
inline cp operator*(const cp &s)const{int real=(1ll*r*s.r%mod+1ll*I*i%mod*s.i%mod)%mod,imag=(1ll*r*s.i%mod+1ll*i*s.r%mod)%mod;return cp{real,imag};}
};
inline cp qpow(cp a,int b){
cp ans=1;
while(b){
if(b&1)ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
inline bool check(int x){return qpow(cp(x),(mod-1)>>1)==1;}
inline pair<int,int> getsqrt(int n){
int a=rand()%mod;
while(!a||check((1ll*a*a-n+mod)%mod))a=rand()%mod;
I=(1ll*a*a-n+mod)%mod;
int x=qpow(cp(a,1),(mod+1)>>1).r;
return make_pair(x,mod-x);
}
inline int get(int n){
pair<int,int>ans=getsqrt(n);
if(ans.first>ans.second)swap(ans.first,ans.second);
return ans.first;
}
}
}
using namespace IO;
using namespace Math;
namespace Polynomial{
struct poly{
vector<int>f;
inline poly(int val=0):f(val){}
inline poly(const vector<int>&g):f(g){}
inline poly(const poly&g):f(g.f){}
inline int operator[](int p)const{return f[p];}
inline int &operator[](int p){return f[p];}
inline vector<int>::iterator begin(){return f.begin();}
inline vector<int>::iterator end(){return f.end();}
inline int size()const{return f.size();}
inline void resize(int n){f.resize(n);}
inline poly slice(int d)const{
poly ret(f);ret.resize(d);
return ret;
}
inline int calc(int x)const{
int ans=0,tmp=1;
for(int i=0;i<f.size();i++){
ans=(ans+1ll*f[i]*tmp)%mod;
tmp=1ll*tmp*x%mod;
}
return ans;
}
inline poly operator+(const poly &p)const{
int d=max(size(),p.size()),mn=min(size(),p.size());
poly ans(d);
for(int i=0;i<mn;i++)ans[i]=add(f[i],p[i]);
if(size()<p.size())for(int i=mn;i<d;i++)ans[i]=p[i];
else for(int i=mn;i<d;i++)ans[i]=f[i];
return ans;
}
inline poly operator-()const{
poly ans(f);
for(int i=0;i<f.size();i++)ans[i]=sub(0,ans[i]);
return ans;
}
inline poly operator-(const poly&p)const{
return operator+(-p);
}
inline friend poly operator+(poly a,int b){
a[0]=add(a[0],b);
return a;
}
inline friend poly operator+(int b,poly a){
a[0]=add(a[0],b);
return a;
}
inline friend poly operator-(poly a,int b){
a[0]=sub(a[0],b);
return a;
}
inline friend poly operator-(int b,poly a){
return b+(-a);
}
inline friend poly operator*(poly a,int b){
int n=a.size();
for(int i=0;i<n;i++)a[i]=1ll*a[i]*b%mod;
return a;
}
inline friend poly operator*(int b,poly a){
int n=a.size();
for(int i=0;i<n;i++)a[i]=1ll*a[i]*b%mod;
return a;
}
inline poly operator<<(int d)const{
poly ans(d+size());
for(int i=0;i<size();i++)ans[i+d]=f[i];
return ans;
}
inline poly operator>>(int d)const{
if(d>=size())return poly(0);
return vector<int>(f.begin()+d,f.end());
}
inline friend poly dao(poly p){
int n=p.size();
for(int i=1;i<n;i++)p[i-1]=1ll*p[i]*i%mod;p[n-1]=0;
return p;
}
inline friend poly jifen(poly p){
int n=p.size();
for(int i=n-1;i>=1;i--)p[i]=1ll*p[i-1]*inv[i]%mod;p[0]=0;
return p;
}
};
namespace NTT{
int wl;
unsigned long long w[2100010];
const unsigned __int128 mod2=mod;
inline void get(int n){
wl=1;
while(wl<n)wl<<=1;
}
inline void init(int n){
int t=1;
while((1<<t)<n)t++;
t=min(t-1,21);
w[0]=1;w[1<<t]=qpow(31,1<<21-t);inv[1]=1;
for(int i=t;i>=1;i--)w[1<<i-1]=1ll*w[1<<i]*w[1<<i]%mod;
for(int i=1;i<(1<<t);i++)w[i]=1ll*w[i&i-1]*w[i&-i]%mod;
for(int i=0;i<=(1<<t);i++)w[i]=(((unsigned __int128)w[i]<<64)+mod-1)/mod;
for(int i=2;i<=n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
jc[0]=Inv[0]=1;
for(int i=1;i<=n;i++)jc[i]=1ll*jc[i-1]*i%mod,Inv[i]=1ll*Inv[i-1]*inv[i]%mod;
}
inline void DIF(poly &a){
int n=a.size();
for(int mid=n>>1;mid;mid>>=1){
for(int i=0,k=0;i<n;i+=mid<<1,k++){
for(int j=0;j<mid;j++){
int x=a[i+j],y=(unsigned)a[i+j+mid]*w[k]*mod2>>64;
a[i+j]=add(x,y);a[i+j+mid]=sub(x,y);
}
}
}
}
inline void DIT(poly &a){
int n=a.size();
for(int mid=1;mid<n;mid<<=1){
for(int i=0,k=0;i<n;i+=mid<<1,k++){
for(int j=0;j<mid;j++){
int x=a[i+j],y=a[i+j+mid];
a[i+j]=add(x,y);a[i+j+mid]=sub(x,y);
a[i+j+mid]=(unsigned)a[i+j+mid]*w[k]*mod2>>64;
}
}
}
for(int i=1;i<=(n-1)>>1;i++)swap(a[i],a[n-i]);
int inv=qpow(n,mod-2);
for(int i=0;i<n;i++)a[i]=1ll*a[i]*inv%mod;
}
}
using namespace NTT;
inline poly operator*(poly f,poly g){
if(max(f.size(),g.size())<=128){
poly ret(f.size()+g.size()-1);
for(int i=0;i<f.size();i++){
for(int j=0;j<g.size();j++){
ret[i+j]=(ret[i+j]+1ll*f[i]*g[j])%mod;
}
}
return ret;
}
int n=f.size(),m=g.size();
get(n+m);
f.resize(wl);g.resize(wl);
DIF(f);DIF(g);
for(int i=0;i<wl;i++)f[i]=1ll*f[i]*g[i]%mod;
DIT(f);
return f.slice(n+m-1);
}
inline poly operator^(poly f,poly g){
int n=f.size(),m=g.size();
get(n);
reverse(g.begin(),g.end());
f.resize(wl);g.resize(wl);
DIF(f);DIF(g);
for(int i=0;i<wl;i++)f[i]=1ll*f[i]*g[i]%mod;
DIT(f);
for(int i=m-1;i<n;i++)f[i-m+1]=f[i];
return f.slice(n-m+1);
}
inline poly getinv(poly f){
int n=f.size();get(n);
f.resize(wl);
poly g(wl),tmp,ret;
g[0]=qpow(f[0],mod-2);
for(int len=2;len<=wl;len<<=1){
tmp.resize(len);ret.resize(len);
for(int i=0;i<len;i++)tmp[i]=f[i];
for(int i=0;i<(len>>1);i++)ret[i]=g[i];
DIF(tmp);DIF(ret);
for(int i=0;i<len;i++)tmp[i]=1ll*tmp[i]*ret[i]%mod;
DIT(tmp);
for(int i=1;i<(len>>1);i++)tmp[i]=0;tmp[0]=mod-1;
DIF(tmp);
for(int i=0;i<len;i++)ret[i]=1ll*tmp[i]*ret[i]%mod;
DIT(ret);
for(int i=len>>1;i<len;i++)g[i]=sub(0,ret[i]);
}
return g.slice(n);
}
inline poly operator/(poly a,poly b){
int n=a.size(),m=b.size();
poly q(a),f(b);
reverse(q.begin(),q.end());
reverse(f.begin(),f.end());
f.resize(n-m+1);f=getinv(f);
q=q*f;q.resize(n-m+1);reverse(q.begin(),q.end());
return q;
}
inline poly operator%(poly a,poly b){
int n=a.size(),m=b.size();
poly q=a/b;b=b*q;
poly r=a-b;
return r.slice(m-1);
}
inline pair<poly,poly> quo(poly a,poly b){
int n=a.size(),m=b.size();
poly q=a/b;
b=b*q;
poly r=a-b;r.resize(m-1);
return make_pair(q,r);
}
namespace CDQ{
poly F[20][8],G[20][8];
inline void brute(poly &f,poly &g,int l,int r,void relax(poly &f,poly &g,int i)){
relax(f,g,l);
for(int i=l+1;i<=r;i++){
for(int j=l;j<i;j++){
int x=1ll*f[j]*g[i-j]%mod;
f[i]=add(f[i],x);
}
relax(f,g,i);
}
}
void cdq(int l,int r,int dep,poly &f,poly &g,void relax(poly &f,poly &g,int i)){
if(r-l+1<=32){
brute(f,g,l,r,relax);return;
}
if(l>=r)return;
int d=1<<((dep-1)*3);
poly tmp(d<<1);
for(int i=0;;i++){
int L=l+i*d,R=min(r,L+d-1);
if(i){
for(int j=0;j<(d<<1);j++)tmp[j]=0;
for(int j=0;j<i;j++){
for(int k=0;k<(d<<1);k++){
int x=1ll*F[dep][j][k]*G[dep][i-j][k]%mod;
tmp[k]=add(tmp[k],x);
}
}
DIT(tmp);
for(int i=L;i<=R;i++)f[i]=add(f[i],tmp[i-L+d]);
}
cdq(L,R,dep-1,f,g,relax);
if(R==r)return;
for(int j=0;j<(d<<1);j++)F[dep][i][j]=0;
for(int j=L;j<=R;j++)F[dep][i][j-L]=f[j];
DIF(F[dep][i]);
}
}
inline void solve(poly &f,poly &g,int n,void relax(poly &f,poly &g,int i)){
if(n<=128){
brute(f,g,0,n-1,relax);return;
}
int len=1,dep=0;
while(len<n)len<<=3,dep++;len>>=3;
for(int i=1;i<=dep;i++){
int d=1<<((i-1)*3),mn=min((n-1)/d,7);
for(int j=1;j<=mn;j++){
int l=(j-1)*d+1,r=min(n-1,(j+1)*d-1);
F[i][j-1].resize(d<<1);G[i][j].resize(d<<1);
for(int k=0;k<(d<<1);k++)G[i][j][k]=0;
for(int k=l;k<=r;k++)G[i][j][k-l+1]=g[k];
DIF(G[i][j]);
}
}
cdq(0,n-1,dep,f,g,relax);
}
}
using namespace CDQ;
inline void relaxln(poly&f,poly &g,int i){
if(!i)f[i]=0;
else f[i]=(1ll*i*g[i]-f[i]+mod)%mod;
}
inline void relaxexp(poly &f,poly &g,int i){
if(!i)f[i]=1;
else f[i]=1ll*f[i]*inv[i]%mod;
}
inline poly ln(poly f){
int n=f.size();
poly g(n);
solve(g,f,n,relaxln);
g[0]=0;
for(int i=1;i<n;i++)g[i]=1ll*g[i]*inv[i]%mod;
return g;
}
inline poly exp(poly f){
int n=f.size();
for(int i=0;i<n;i++)f[i]=1ll*f[i]*i%mod;
poly g(n);
solve(g,f,n,relaxexp);
return g;
}
inline poly qpow(poly f,int k){
int n=f.size();
f=ln(f);
for(int i=0;i<n;i++)f[i]=1ll*k*f[i]%mod;
f=exp(f);
return f;
}
inline poly qpow(poly f,int k1,int k2,int k3){
int n=f.size();
poly g(n);
if(f[0]==0&&k3>=n)return g;
int pos;
for(int i=0;i<n;i++){
if(f[i]){
pos=i;break;
}
}
if(1ll*pos*k1>=n)return g;
int inv=::qpow(f[pos],mod-2),p=::qpow(f[pos],k2);
for(int i=0;i<n-pos;i++)f[i]=1ll*f[i+pos]*inv%mod;
for(int i=n-pos;i<n;i++)f[i]=0;
f=ln(f);
for(int i=0;i<n;i++)f[i]=1ll*f[i]*k1%mod;
f=exp(f);
pos*=k1;
for(int i=n-1;i>=pos;i--)g[i]=1ll*f[i-pos]*p%mod;
return g;
}
inline poly sqrt(poly f,int tp=1){
int n=f.size();get(n);
f.resize(wl);
poly g(wl),g2(wl),h(wl),tmp,ret(1),ans;
g[0]=g2[0]=Cipolla::get(f[0]);h[0]=::qpow(g[0],mod-2);
for(int len=2;len<=wl;len<<=1){
ans.resize(len);tmp.resize(len);
for(int i=0;i<(len>>1);i++)tmp[i]=h[i],ret[i]=1ll*g2[i]*g2[i]%mod;
DIT(ret);
for(int i=0;i<(len>>1);i++)ans[i+(len>>1)]=sub(sub(ret[i],f[i]),f[i+(len>>1)]),ans[i]=0;
DIF(ans);DIF(tmp);
for(int i=0;i<len;i++)ans[i]=1ll*ans[i]*tmp[i]%mod*inv[2]%mod;
DIT(ans);
for(int i=len>>1;i<len;i++)g[i]=sub(0,ans[i]);
if(len!=wl||tp==-1){
ret.resize(len);
for(int i=0;i<len;i++)ret[i]=g[i];
DIF(ret);
for(int i=0;i<len;i++)g2[i]=ret[i],ret[i]=1ll*ret[i]*tmp[i]%mod;
DIT(ret);
for(int i=1;i<(len>>1);i++)ret[i]=0;ret[0]=mod-1;
DIF(ret);
for(int i=0;i<len;i++)ret[i]=1ll*ret[i]*tmp[i]%mod;
DIT(ret);
for(int i=len>>1;i<len;i++)h[i]=sub(0,ret[i]);
}
}
if(tp==1)return g.slice(n);
else return h.slice(n);
}
inline poly move(poly a,int k){
int n=a.size();get(n<<1);
poly b(n);
for(int i=0,pw=1;i<n;i++,pw=1ll*pw*k%mod)a[i]=1ll*a[i]*jc[i]%mod,b[i]=1ll*pw*Inv[i]%mod;
reverse(a.begin(),a.end());
a=a*b;a.resize(n);
reverse(a.begin(),a.end());
for(int i=0;i<n;i++)a[i]=1ll*a[i]*Inv[i]%mod;
return a;
}
inline poly movepoint(poly f,int m){
int n=f.size()-1;
poly g(n<<1|1);
static int mjc[300010],minv[300010];mjc[0]=minv[0]=1;
for(int i=1;i<=2*n+1;i++)mjc[i]=1ll*mjc[i-1]*(m-n-1+i)%mod;
minv[n<<1|1]=::qpow(mjc[n<<1|1],mod-2);
for(int i=n<<1;i>=1;i--)minv[i]=1ll*minv[i+1]*(m-n+i)%mod;
for(int i=0;i<=n;i++){
f[i]=1ll*f[i]*Inv[i]%mod*Inv[n-i]%mod;
if(n-i&1)f[i]=sub(0,f[i]);
}
for(int i=0;i<=(n<<1);i++)g[i]=1ll*minv[i+1]*mjc[i]%mod;
get(n+1<<1);
f.resize(wl);g.resize(wl);DIF(f);DIF(g);
for(int i=0;i<wl;i++)f[i]=1ll*f[i]*g[i]%mod;DIT(f);
for(int i=n;i<=(n<<1);i++)f[i-n]=1ll*mjc[i+1]*minv[i-n]%mod*f[i]%mod;
return f;
}
namespace Multipoint{
poly F[400010],G[400010];
#define lson rt<<1
#define rson rt<<1|1
void build(int rt,int l,int r,poly&a){
if(l==r){
G[rt].resize(2);
G[rt][0]=1;G[rt][1]=sub(0,a[l]);
return;
}
int mid=(l+r)>>1;
build(lson,l,mid,a);build(rson,mid+1,r,a);
G[rt]=G[lson]*G[rson];
}
void query(int rt,int l,int r,poly &a){
if(l==r){
a[l]=F[rt][0];return;
}
int mid=(l+r)>>1;
F[lson]=F[rt]^G[rson];F[rson]=F[rt]^G[lson];
query(lson,l,mid,a);query(rson,mid+1,r,a);
}
poly multipoint(poly a,poly b,int n,int m){
build(1,1,m,b);
poly inv=getinv(G[1]);
reverse(inv.begin(),inv.end());
poly tmp=a*inv;
F[1].resize(m+1);
for(int i=n;i<n+m;i++)F[1][i-n]=tmp[i];
poly ans(m+1);
query(1,1,m,ans);
for(int i=1;i<=m;i++)ans[i]=(1ll*ans[i]*b[i]+a[0])%mod;
return ans;
}
#undef lson
#undef rson
}
using Multipoint::multipoint;
namespace Multipoly{
#define lson rt<<1
#define rson rt<<1|1
poly F[400010],G[400010];
void build(int rt,int l,int r,poly&a){
if(l==r){
G[rt].resize(2);
G[rt][0]=sub(0,a[l]);G[rt][1]=1;
return;
}
int mid=(l+r)>>1;
build(lson,l,mid,a);build(rson,mid+1,r,a);
G[rt]=G[lson]*G[rson];
}
void query(int rt,int l,int r,poly&y){
if(l==r){
F[rt].resize(2);
F[rt][0]=y[l];return;
}
int mid=(l+r)>>1;
query(lson,l,mid,y);query(rson,mid+1,r,y);
F[rt]=F[lson]*G[rson]+F[rson]*G[lson];
}
poly getpoly(int n,poly x,poly y){
build(1,1,n,x);
poly tmp(n+1),ans(n);
for(int i=0;i<=n;i++)tmp[i]=G[1][i];
tmp=dao(tmp);
poly ret=multipoint(tmp,x,n+1,n);
for(int i=1;i<=n;i++)y[i]=1ll*y[i]*::qpow(ret[i],mod-2)%mod;
query(1,1,n,y);
for(int i=0;i<n;i++)ans[i]=F[1][i];
return ans;
}
#undef lson
#undef rson
}
using Multipoly::getpoly;
// namespace Downpower{
// inline poly mul(poly f,poly g){}
// inline poly SimpToDown(poly f){}
// inline poly DownToSimp(poly f){}
// }
inline poly chirpz(poly f,int k,int m){
int n=f.size();
static int c[2100010],invc[2100010];
c[0]=invc[0]=1;c[1]=k;invc[1]=::qpow(c[1],mod-2);
for(int i=2;i<=n+m;i++)c[i]=1ll*c[i-1]*c[1]%mod,invc[i]=1ll*invc[i-1]*invc[1]%mod;
poly g(n+m+1);g[0]=1;
for(int i=1;i<=n+m;i++){
c[i]=1ll*c[i]*c[i-1]%mod;invc[i]=1ll*invc[i]*invc[i-1]%mod;
g[i]=c[i-1];
}
for(int i=0;i<n;i++){
f[i]=1ll*f[i]*(i?invc[i-1]:1)%mod;
}
f.resize(n+1);
reverse(f.begin(),f.end());
get(n+m);
f.resize(wl);g.resize(wl);
DIF(f);DIF(g);
for(int i=0;i<wl;i++)f[i]=1ll*f[i]*g[i]%mod;
DIT(f);
for(int i=0;i<m;i++)f[i]=1ll*f[i+n]*(i?invc[i-1]:1)%mod;
return f.slice(m);
}
inline poly sin(poly f){
const int I=::qpow(3,(mod-1)>>2);
return (exp(I*f)-exp((mod-I)*f))*::qpow(2ll*I%mod,mod-2);
}
inline poly asin(poly f){
int n=f.size();
return jifen((dao(f)*sqrt(1-(f*f).slice(n),-1)).slice(n));
}
inline poly cos(poly f){
const int I=::qpow(3,(mod-1)>>2);
return (exp(I*f)+exp((mod-I)*f))*(mod+1>>1);
}
inline poly acos(poly f){
return -asin(f);
}
inline poly tan(poly f){
int n=f.size();
return (sin(f)*getinv(cos(f))).slice(n);
}
inline poly atan(poly f){
int n=f.size();
return jifen((dao(f)*getinv(1+(f*f).slice(n))).slice(n));
}
}
using namespace Polynomial;
int n,k;
int main(){
n=read()+1;k=read();init(n<<1);
poly a(n);
for(int i=0;i<n;i++)a[i]=read();
a=dao(qpow(1+ln(2+a-a[0]-exp(jifen(sqrt(a,-1)))),k));
for(int i=0;i<n-1;i++)print(a[i]),putchar(' ');puts("");
return 0;
}