大致题意： 给定(n,x)和一个(m)次多项式(f(k))，求(sum_{k=0}^nf(k) imes x^k imes C_n^k)。
下降幂
首先不难想到要把(f(k))拆开。
然而，这道题妙就妙在，它的第一步是把(f(k))转化为下降幂形式，即令：
[f(k)=sum_{i=0}^ma_ik^i=sum_{i=0}^mb_ik^{underline{i}}
]
由于此处(mle1000)，因此我们只要(O(m^2))暴力转就可以了。
关于第二类斯特林数与下降幂有一个公式：
[x^n=sum_{i=0}^nS2(n,i) imes x^{underline{i}}
]
（根据式子本身意义理解，左式(x^n)就是假设所有盒子本质不同的方案数，右式就是枚举非空盒子个数求出对应方案数）
所以可以得到：
[f(k)=sum_{i=0}^ma_ik^i=sum_{i=0}^ma_isum_{j=0}^iS2(i,j)k^{underline{j}}=sum_{i=0}^m(sum_{j=i}^mS2(j,i) imes a_j)k^{underline{i}}
]
即：
[b_i=sum_{j=i}^mS2(j,i) imes a_j
]
推式子
好了，现在我们已经把(f(k))转化成了下降幂形式，接着就是把它代入：
[sum_{k=0}^nsum_{i=0}^mb_ik^{underline{i}} imes x^k imes C_n^k
]
显然把(i)的枚举调到前面去得到：
[sum_{i=0}^mb_isum_{k=0}^nk^{underline{i}} imes x^k imes C_n^k
]
接下来介绍一个新的公式：
[k^{underline{i}} imes C_n^k=n^{underline{i}} imes C_{n-i}^{k-i}
]
证明就是暴拆：
[k^{underline{i}} imes C_n^k=frac{k!}{(k-i)!} imes frac{n!}{k!(n-k)!}=frac{n!}{(k-i)!(n-k)!}
]
[n^{underline{i}} imes C_{n-i}^{k-i}=frac{n!}{(n-i)!} imes frac{(n-i)!}{(k-i)!(n-k)!}=frac{n!}{(k-i)!(n-k)!}
]
套用这个公式得到：
[sum_{i=0}^mb_in^{underline{i}}sum_{k=0}^n C_{n-i}^{k-i} imes x^k
]
由于(k-i<0)时组合数没用，因此索性令(k)枚举(k-i)，得到：
[sum_{i=0}^mb_in^{underline{i}}sum_{k=0}^{n-i} C_{n-i}^k imes x^{k+i}
]
从(x^{k+i})中提出一个(x_i)：
[sum_{i=0}^mb_in^{underline{i}}x^isum_{k=0}^{n-i} C_{n-i}^k imes x^{k}
]
然后后面这家伙显然就是一个二项式定理啊：
[sum_{i=0}^mb_in^{underline{i}}x^i(x+1)^{n-i}
]
于是就做完了，这个式子可以直接暴力算。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define M 1000
using namespace std;
int n,m,x,X,a[M+5],b[M+5],Fac[M+5],S2[M+5][M+5];
I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
int main()
{
RI i,j;scanf("%d%d%d%d",&n,&x,&X,&m);
for(S2[0][0]=i=1;i<=m;++i) for(S2[i][0]=0,j=1;j<=i;++j) S2[i][j]=(1LL*S2[i-1][j]*j+S2[i-1][j-1])%X;//预处理第二类斯特林数
for(i=0;i<=m;++i) scanf("%d",a+i);for(i=0;i<=m;++i) for(j=i;j<=m;++j) b[i]=(1LL*S2[j][i]*a[j]+b[i])%X;//多项式转下降幂
RI t=0,n_=1;for(i=0;i<=m;n_=1LL*n_*(n-i)%X,++i) t=(1LL*b[i]*n_%X*QP(x,i)%X*QP(x+1,n-i)+t)%X;//计算答案，n_记录n的i次下降幂
return printf("%d
",t),0;//输出答案
}