题目
计算 (left(sumlimits_{k=0}^n f(k) imes x^k imes dbinom{n}{k} ight)mod p) ， (f(k) = sumlimits_{i=0}^m a_i imes k^i) , (n,k,p,m,a_i) 给定。
前言
前几天考了一道类似的题目，当时本蒟蒻考场自闭，考后，听说有此题，便做了一下，因为我比较菜，所以这篇题解主要以一个不会多项式（虽然此题不要）、没怎么推过式子的蒟蒻角度做题。
前置基础
1.会组合数的定义，知道其性质，怎么求
2.了解斯特林数，会它的通项公式，一些小性质就行了
3.知道二项式定理（认得长什么样就行了）
（这些东西具体性质后面会讲，会解释，只要了解就可以继续看下去了）
思路
先合并成一个式子：
(left(sumlimits_{k=0}^n sumlimits_{i=0}^m a_i imes k^i imes x^k imes dbinom{n}{k} ight)mod p) 。
我们再看一下数据范围
(n in [1,10^9],k in[0,n], m in [0,min(n,1000)])
那么，我们一定不能去暴力算 (k) ，我们要想办法将有关 (k) 的项全部变成 与 (m) （或和 (m) 一样小的） 有关的项。
(p) 不一定是质数
这题很可能不是多项式
因为 (n) 很大，我们只能处理出 (k!mod p) 和 (k!) 在 (p) 下的逆元（这是一种组合数的求法）。但 (p) 不是质数，有的数没有逆元，我们就要想办法除去组合数。（这里可能有点不严谨，但反正很难求出这个组合数）
综上，
我们有两个目标：
目标一
将有关 (k) 的项全部变成 与 (m) （或和 (m) 一样小的） 有关的项。
目标二
除去组合数
具体步骤
(left(sumlimits_{k=0}^n sumlimits_{i=0}^m a_i imes k^i imes x^k imes dbinom{n}{k} ight)mod p)
对于目标一
(k^i) 最难搞，我们先消去 (k^i) ，这里要用第二类斯特林数，(left{_m^n ight}) 代表 (n) 个球放入 (m) 个集合中的方案数。
(k^i = sumlimits_{j = 0}^k left{^i_j ight} dbinom{k}{j}j!)
考虑组合意义： (k^i) 代表将(i) 个球放入(k) 个互不相同盒子中（可以为空），
我们这个展开就是先讨论要将这些球放入(j) 个相同盒子中（不能为空），即选盒子的方案数乘上将球放入这些盒子的方案数： (left{^i_j ight} dbinom{k}{j}) ，
又因为我们要求的是不同的盒子中，我们再乘上一个 (j!)。
值得注意的是，当 (j > i) 时， (left{^i_j
ight}) 没有意义，为了不择手段地 消去 (k) ,我们可以将求和上界改为 (i) ：
(k^i = sumlimits_{j = 0}^i left{^i_j ight} dbinom{k}{j}j!)
至于 (x^k) 这样展开复杂了，我们先放到一边。
对于目标二
我们的式子已经变成了：
(left(sumlimits_{k=0}^n sumlimits_{i=0}^m a_i imes sumlimits_{j = 0}^i left{^i_j ight} dbinom{k}{j}j! imes x^k imes dbinom{n}{k} ight)mod p)
我们可以看到有两个组合数：
(dbinom{k}{j} imes dbinom{n}{k})
再次考虑组合意义：
先从 (n) 个球中选出 (k) 个球，再从中选出 (j) 个球，
这就等价于
先选出 (j) 个球作为最后的方案，再从选 (n-j) 个球中选出 (k-j) 个球作为第一次还要选的球，
所以，
(dbinom{k}{j} imes dbinom{n}{k} = dbinom{n-j}{k-j} imes dbinom{n}{j})
但是组合数还是没有消失，我们的式子变成了：
(left(sumlimits_{k=0}^n sumlimits_{i=0}^m a_i imes sumlimits_{j = 0}^i left{^i_j ight} dbinom{n-j}{k-j} imes dbinom{n}{j}j! imes x^k ight)mod p)
调一下顺序：
(left( sumlimits_{i=0}^m a_isumlimits_{j=0}^ileft{^i_j ight} imesdbinom{n}{j}j! imes sumlimits_{k=0}^ndbinom{n-j}{k-j}x^k ight)mod p)
接下来，非常重要，
观察到
(dbinom{n-j}{k-j}x^k)
我们知道二项式定理：
((x+y)^n = sumlimits_{i =0}^n dbinom{n}{i} imes x^i y^{n-i}) ,那么，我们可以尽量让上面的式子变为二项式定理，
如果是这样就好了：
(sumlimits_{k=0}^ndbinom{n-j}{k-j}x^{k-j} = (x+1)^{n-j}) (二项式定理)
那我们就强行补一下：
(sumlimits_{k=0}^ndbinom{n-j}{k-j}x^{k} = sumlimits_{k=0}^ndbinom{n-j}{k-j}x^{k-j} imes x^j = (x+1)^{n-j} imes x^j)
原式简单多了：
(left( sumlimits_{i=0}^m a_isumlimits_{j=0}^ileft{^i_j ight} imesdbinom{n}{j}j! imes (x+1)^{n-j} imes x^j ight)mod p)
离目标最后一步！
(dbinom{n}{j}j! = frac{n!}{j! imes(n-j)!} imes j! = frac{n!}{(n-j)!} = n imes (n-1) imes dots imes(n-j+1))
因为 (j) 十分小，我们就可以再循环的时候一边计算这个式子就行了。
答案：
(left( sumlimits_{i=0}^m a_isumlimits_{j=0}^ileft{^i_j ight} imesfrac{n!}{(n-j)!} imes (x+1)^{n-j} imes x^j ight)mod p) ，
我们只要 (O(k^2)) 推斯特林数就行了，其他项在循环时可以算出来。
代码
const int MAXN = 5010;
typedef long long ll;
ll a[MAXN],strling[MAXN][MAXN],n,x,p,m,x1j[MAXN];
ll qp(ll x,ll t){
ll res = 1;
for(;t;t >>= 1,x = x*x%p){
if(t&1) res = res * x % p;
}
return res;
}
int main (){
scanf("%lld %lld %lld %lld",&n,&x,&p,&m);
for(int i = 0;i <= m;i++) scanf("%lld",&a[i]);
strling[0][0] = 1;
for(int i = 1;i <= m;i++)
for(int j = 1;j <= i;j++)
strling[i][j] = (strling[i-1][j-1] + strling[i-1][j] * j %p)%p;
//斯特林数
ll ans = 0;
for(int i = 0;i <= m;i++){
ll tot = 0;
ll fac = 1ll,xj = 1ll;
x1j[i] = qp(x+1,n-i);
for(int j = i-1;j >= 0;j--){
x1j[j] = x1j[j+1] * (x+1) % p;
}//循环时处理 (x+1)^{n-j},n * (n-1) *...*(n-j+1)
for(int j = 0;j <= i;j++){
tot = (tot + strling[i][j] * fac % p* xj % p*x1j[j]%p)%p;
fac = fac * (n-j)%p;
xj = xj*x%p;
}
tot = tot * a[i]%p;
ans = (ans + tot)%p;
}
printf("%lld
",ans);
return 0;
}