uoj269 【清华集训2016】如何优雅地求和

设$f(x)=\sum_{k=0}^ma_kx^k$。根据乘法分配律，可以将答案拆成$a_iQ(k^i,n,x)$的和。那么我们现在只需要关心$f(x)=x^0,x^1,x^2,…,x^m$时如何快速求和。

$f(x)=1$时，首先由二项式定理，$Q=1$。

$f(x)=x$时，可以这样化简：

$Q=\sum_{k=0}^nk\frac{n!}{k!(n-k)!}x^k(1-x)^{n-k}=\sum_{k=0}^nnx\frac{(n-1)!}{(k-1)!(n-k)!}x^{k-1}(1-x)^{n-k}=nx\sum_{k=0}^n\Big(^{n-1}_{k-1}\Big)x^{k-1}(1-x)^{n-k}=nx$

然后发现当$f(x)=x^2$时就似乎无法化简了。

考虑$f(x)=x$时我们的化简方式：注意到后面的形式极容易想到用二项式定理来做，那么我们就把原来的组合数通过某种方式变成能够用二项式定理的新的组合数。能否这样化简取决于$f(x)$是什么。观察发现有这样的结论：

$当f(x)=x^{\underline{d}}时，Q=n^{\underline{d}}x^d$

化简方式与$f(x)=x$时相似，具体来说：

$Q=\sum_{k=0}^nk^{\underline{d}}\frac{n!}{k!(n-k)!}x^k(1-x)^{n-k}=\sum_{k=0}^nn^{\underline{d}}x^d\frac{(n-d)!}{(k-d)!(n-k)!}x^{k-d}(1-x)^{n-k}=n^{\underline{d}}x^d$

如果我们能把$f(x)$写成下降幂的和的形式，即求出$f(x)=\sum_{k=0}^mb_kx^{\underline{k}}$当中的$b_k$，那么显然扫一遍就能得到答案了。现在考虑如何求$b_k$。

令$c_k=b_kk!$，那么有：

$f(x)=\sum_{k=0}^mc_k\frac{x^{\underline{k}}}{k!}=\sum_{k=0}^mc_k\Big(^{x}_{k}\Big)$

注意到题目还有一个条件没有用到：题目中给出了$x=0,1,2,…,m$时$f(x)$的值。

显然，当$x=0$时，$f(x)=c_0$。

考虑$\triangle f(x)=f(x+1)-f(x)$，注意到$C_{x+1}^{k}-C_{x}^{k}=C_x^{k-1}$，有$\triangle f(x)=\sum_{k=1}^mc_k\Big(^{x}_{k-1}\Big)$，那么当$x=0$时，$\triangle f(x)=c_1$。

不难看出，$\triangle^{k} f(0)=c_k$。

虽然这里的步骤可以用FFT优化，但是由于本题中$m\leq20000$，~~懒惰的~~良心的出题人给的std也是$O(m^2)$的算法，所以暴力求即可。

#include<stdio.h>
#include<algorithm>
#include<cstring>
#define rg register
#define ll long long
#define MAXN 20005
using namespace std;
const int mod=998244353;

int add(int a,int b){a+=b;a-=a<mod?0:mod;return a;}
int sub(int a,int b){a-=b;a+=a<0?mod:0;return a;}
int mul(int a,int b){return (ll)a*b%mod;}
int ksm(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=mul(ans,a);
		b>>=1;a=mul(a,a);
	}
	return ans;
}

int N,M,X,f[MAXN],b[MAXN],Ans;

int main(){
	rg int i,j;
	int tmp;
	scanf("%d%d%d",&N,&M,&X);
	for(i=0;i<=M;i++)scanf("%d",&f[i]);
	
	for(i=0;i<=M;i++){
		b[i]=f[0];
		for(j=0;j<M-i;j++)f[j]=sub(f[j+1],f[j]);
	}
	
	tmp=1;
	for(i=0;i<=M;i++){
		Ans=add(Ans,mul(tmp,b[i]));
		tmp=mul(tmp,X);
		tmp=mul(tmp,N-i);
		tmp=mul(tmp,ksm(i+1,mod-2));
	}
	printf("%d\n",Ans);
}