uoj#269. 【清华集训2016】如何优雅地求和（数论）

首先，如果$f(x)=1$，那么根据二项式定理，有$Q(f,n,k)=1$

当$f(x)=x$的时候，有$$Q=\sum_{i=0}^ni\times \frac{n!}{i!(n-i)!}k{n-i}$$

\[Q=\sum_{i=0}^nnk\times \frac{(n-1)!}{(i-1)!(n-i)!}k^{i-1}(1-k)^{n-i}
\]

\[Q=nk\sum_{i=0}^n\frac{(n-1)!}{(i-1)!(n-i)!}k^{i-1}(1-k)^{n-i}
\]

\[Q=nk\sum_{i=0}^n{n-1\choose i-1}k^{i-1}(1-k)^{n-i}
\]

根据二项式定理后面的等于$1$，所以$Q=nk$

然后我们发现，如果$f(x)=x^{\underline{d}}$，则有$Q=n^{\underline{d}}k^d$，其中$x^{\underline{d}}$是$x$的$d$次下降幂，为$x(x-1)...(x-d+1)$，证明和上面的差不多当

\[Q=\sum_{i=0}^ni^{\underline{d}}\times \frac{n!}{i!(n-i)!}k^i(1-k)^{n-i}
\]

\[Q=\sum_{i=0}^nn^{\underline{d}}x^d\times \frac{(n-d)!}{(i-d)!(n-i)!}k^{i-d}(1-k)^{n-i}
\]

\[Q=n^{\underline{d}}k^d\sum_{i=0}^n \frac{(n-d)!}{(i-d)!(n-i)!}k^{i-d}(1-k)^{n-i}
\]

\[Q=n^{\underline{d}}k^d\sum_{i=0}^n{n-d\choose i-d}k^{i-d}(1-k)^{n-i}
\]

后面那个还是等于$1$

根据乘法分配律，如果$f(x)=\sum_{i=0}^m a_ix^{\underline{i}}$，那么$Q(f,n,x)=\sum_{i=0}^m a_i\times Q(x^{\underline{i}},n,k)$

考虑如何计算$a_i$，记$b_i=\frac{a_i}{i!}$，那么$f(x)=\sum_{i=0}^m b_i\frac{x^{\underline{i}}}{i!}=\sum_{i=0}^m b_i{x\choose i}$

不要忘了我们已知$x=0,1,...,m$时$f(x)$的值

当$x=0$时，$f(x)=b_0$

记$\triangle f(x)=f(x+1)-f(x)$，即一阶差分，因为${x+1\choose i}-{x\choose i}={x\choose i-1}$，所有$\triangle f(x)=\sum_{i=1}^m b_i{x\choose i-1}$，那么$\triangle f(0)=b_1$

同理，$\triangle^kf(0)=b_k$，即$k$阶差分后$0$处的值为$b_k$

因为std写的是$O(m^2)$的我们不能辜负出题人的一片好心，所以直接$O(m^2)$暴力就好了（据说这里可以用$FFT优化然而懒了233）

然后没有然后了

//minamoto

#include<bits/stdc++.h>

#define R register

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

const int N=2e4+5,P=998244353;

inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}

inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}

inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}

int ksm(R int x,R int y){

	R int res=1;

	for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);

	return res;

}

int b[N],n,m,k,ans,p=1;

int main(){

//	freopen("testdata.in","r",stdin);

	n=read(),m=read(),k=read();

	fp(i,0,m)b[i]=read();

	fp(i,0,m){

		ans=add(ans,mul(p,b[0]));

		fp(j,0,m-i-1)b[j]=dec(b[j+1],b[j]);

		p=1ll*p*k%P*(n-i)%P*ksm(i+1,P-2)%P;

	}printf("%d\n",ans);

	return 0;

}