非常显然的，我们展开 \(f(k)\)，于是有：
\[\begin{align}
&\sum\limits_{k=0}^{n}\sum\limits_{i=0}^{m}a_{i}k^{i}x^{k}\binom{n}{k}\\
=&\sum\limits_{k=0}^{n}\sum\limits_{i=0}^{m}a_{i}
{\sum\limits_{j=0}^{i}\begin{Bmatrix}i\\j\end{Bmatrix}\binom{k}{j}j!}
x^{k}\binom{n}{k}\\
=&\sum\limits_{i=0}^{m}a_{i}\sum\limits_{j=0}^{i}\begin{Bmatrix}i\\j\end{Bmatrix}j!\sum\limits_{k=0}^{n}x^k\binom{n}{j}\binom{n-j}{k-j}\\
=&\sum\limits_{i=0}^{m}a_{i}\sum\limits_{j=0}^{i}\begin{Bmatrix}i\\j\end{Bmatrix}j!\binom{n}{j}\sum\limits_{k=0}^{n-j}x^{k+j}\binom{n-j}{k}\\
=&\sum\limits_{i=0}^{m}a_{i}\sum\limits_{j=0}^{i}\begin{Bmatrix}i\\j\end{Bmatrix}n^{\underline{j}}(x+1)^{n-j}x^{j}\\
=&\sum\limits_{i=0}^{m}n^{\underline i}(x+1)^{n-i}x^{i}\sum\limits_{j=i}^{m}a_{j}\begin{Bmatrix}j\\i\end{Bmatrix}
\end{align}
\]
然后就直接\(\mathcal O(m^2)\) 做出这道题。
code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ci = const int;
int n, x, p, m, a[1005];
int S[1005][1005];
int qpow(int x, int y)
{
int z = 1;
while (y)
{
if (y & 1) z = 1ll * z * x % p;
x = 1ll * x * x % p, y >>= 1;
}
return z;
}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
cin >> n >> x >> p >> m;
for (int i = 0; i <= m; ++i) cin >> a[i];
S[0][0] = 1;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= i; ++j)
S[i][j] = (S[i - 1][j - 1] + 1ll * S[i - 1][j] * j) % p;
int ans = 0;
for (int i = 0; i <= m; ++i)
{
ll n1 = 1;
for (int j = 0; j < i; ++j) (n1 *= n - j) %= p;
ll n2 = n1 * qpow(x + 1, n - i) % p * qpow(x, i) % p;
for (int j = i; j <= m; ++j)
(ans += n2 * a[j] % p * S[j][i] % p) %= p;
}
cout << ans;
return 0;
}