wjz：《如何优雅地 AK NOI》
我：如何优雅地爆零
首先，按照这题总结出来的一个小套路，看到多项式与组合数结合的题，可以考虑将普通多项式转为下降幂多项式，因为下降幂和组合数都可以用阶乘相除的形式表示，而对于两个组合数相乘我们有恒等式 (dbinom{n}{m}dbinom{m}{k}=dbinom{n}{k}dbinom{n-k}{m-k})，这样我们可以将原式中待枚举变量 (m) 从两个组合数中转移到一个组合数（(dbinom{n-k}{m-k})）中，也就进而可以用二项式定理等公式化简了。
因此此题我们也可以考虑设 (f(x)=sumlimits_{i=0}^mb_ix^{underline{i}})，下面开始推式子：
[egin{aligned}
ans&=sumlimits_{k=0}^mf(k)dbinom{n}{k}x^k(1-x)^{n-k}\
&=sumlimits_{k=0}^nsumlimits_{j=0}^mb_jk^{underline{j}}dbinom{n}{k}x^k(1-x)^{n-k}\
&=sumlimits_{j=0}^mb_jj!sumlimits_{k=j}^ndbinom{k}{j}dbinom{n}{k}x^k(1-x)^{n-k}\
&=sumlimits_{j=0}^mb_jj!dbinom{n}{j}sumlimits_{k=j}^ndbinom{n-j}{k-j}x^k(1-x)^{n-k}\
&=sumlimits_{j=0}^mb_jj!dbinom{n}{j}sumlimits_{k=0}^{n-j}dbinom{n-j}{k}x^{k+j}(1-x)^{n-k-j}\
&=sumlimits_{j=0}^mb_jj!dbinom{n}{j}x^j(1-x+x)^{n-j}\
&=sumlimits_{j=0}^mb_jj!dbinom{n}{j}x^j
end{aligned}
]
因此我们只需求出 (b_j) 即可在线性的时间内计算出 (ans)。
接下来我们的任务是怎样由 (f(x)) 的点值计算出 (b_i)，考虑 (f(x)) 的 ( ext{EGF})，那么有
[egin{aligned}
sumlimits_{n}dfrac{f(n)x^n}{n!}&=sumlimits_{n}sumlimits_{j=0}^mb_jn^{underline{j}}dfrac{x^n}{n!}\
&=sumlimits_{j=0}^mb_jsumlimits_{n}dfrac{x^n}{(n-j)!}\
&=sumlimits_{j=0}^mb_jx^jsumlimits_{n}dfrac{x^{n-j}}{(n-j)!}
end{aligned}
]
记 (A=sumlimits_{j=0}^mb_jx^j,B=sumlimits_{j}dfrac{x^j}{j!}=e^x)，那么 (sumlimits_{n}dfrac{f(n)x^n}{n!}=A imes B)。
故 (A=(sumlimits_{n}dfrac{f(n)x^n}{n!}) imes e^{-x})，NTT 一下即可。
时间复杂度 (nlog n)。
const int pr=3;
const int MOD=998244353;
const int ipr=(MOD+1)/3;
const int MAXP=1<<16;
int qpow(int x,int e){
int ret=1;
for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
return ret;
}
int rev[MAXP+5];
void NTT(vector<int> &a,int len,int type){
int lg=31-__builtin_clz(len);
for(int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<lg-1);
for(int i=0;i<len;i++) if((i-rev[i])>>31) swap(a[i],a[rev[i]]);
for(int i=2;i<=len;i<<=1){
int W=qpow((type<0)?ipr:pr,(MOD-1)/i);
for(int j=0;j<len;j+=i){
for(int k=0,w=1;k<(i>>1);k++,w=1ll*w*W%MOD){
int X=a[j+k],Y=1ll*w*a[(i>>1)+j+k]%MOD;
a[j+k]=(X+Y)%MOD;a[(i>>1)+j+k]=(X-Y+MOD)%MOD;
}
}
} if(!~type) for(int j=0,ivn=qpow(len,MOD-2);j<len;j++) a[j]=1ll*a[j]*ivn%MOD;
}
vector<int> conv(vector<int> a,vector<int> b){
int LEN=1;while(LEN<a.size()+b.size()) LEN<<=1;a.resize(LEN,0);b.resize(LEN,0);
NTT(a,LEN,1);NTT(b,LEN,1);for(int i=0;i<LEN;i++) a[i]=1ll*a[i]*b[i]%MOD;
NTT(a,LEN,-1);return a;
}
int n,m,x,fac[MAXP+5],ifac[MAXP+5];
void init_fac(int n){
for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i]*ifac[i-1]%MOD;
}
int main(){
scanf("%d%d%d",&n,&m,&x);vector<int> a(m+1),b(m+1);init_fac(m);
for(int i=0;i<=m;i++) scanf("%d",&a[i]),a[i]=1ll*a[i]*ifac[i]%MOD;
for(int i=0;i<=m;i++) b[i]=((~i&1)?ifac[i]:(MOD-ifac[i]));a=conv(a,b);
int ans=0,cur=1;for(int i=0;i<=m;i++) ans=(ans+1ll*a[i]*cur%MOD*qpow(x,i))%MOD,cur=1ll*cur*(n-i)%MOD;
printf("%d
",ans);
return 0;
}