前置知识
二项式定理
\[(x + y)^n = \sum_{i = 0}^n \binom nix^iy^{n - i} \]组合恒等式
\[k \times \binom nk = n \times \binom{n - 1}{k - 1} \]题解
先不管取模的事情。
考虑把 \(f(k)\) 中次数相同的项拿出来，则原式可化为：
\[Ans = a_0 \sum_{k = 0}^n x^k \times \binom nk + \sum_{p = 1}^m a_p \sum_{k = 0}^n\left[k^p \times x^k \times \binom nk\right] \]对第一项用一下 二项式定理，得：
\[Ans = a_0(1 + x)^n + \sum_{p = 1}^m a_p \sum_{k = 0}^n\left[k^p \times x^k \times \binom nk\right] \]其中 \(k^p \times \dbinom nk\) 可以用 组合恒等式 化开，可以写成：
\[\sum_{i = 1}^p A_p(i) \times n^{\underline i} \times \binom{n - i}{k - i} \]\(n^{\underline i}\) 是下降幂，形式化地，\(n^{\underline i} = \prod\limits_{j = n - i + 1}^n j\)。
例如，当 \(p = 2\) 时，
\[k^2 \binom nk = k \times k \binom nk = nk\binom{n - 1}{k - 1} = n(k - 1)\binom{n - 1}{k - 1} + n\binom{n - 1}{k - 1} = n(n - 1)\binom{n - 2}{k - 2} + n\binom{n - 1}{k - 1} \]当 \(p = 3\) 时，
\[k^3\binom nk = k \times k^2\binom nk = k[n(n - 1)\binom{n - 2}{k - 2} + n\binom{n - 1}{k - 1}] = n(n - 1)(n - 2)\binom{n - 3}{k - 3} + 3n(n - 1)\binom{n - 2}{k - 2} + n\binom{n - 1}{k - 1} \]接下来，瓶颈来到了如何求解系数 \(A_p(i)\)（实际上就是第二类斯特林数）。
考虑如何递推求解 \(A_p(i)\)。
回顾一下前面 \(p = 2, 3\) 的推导过程，并结合 \(A_3(2) = 3\) 这一特殊值，不难得出：
\[A_p(i) = iA_{p - 1}(i) + A_{p - 1}(i - 1) \]于是递推求解 \(A_p(i)\) 的时间复杂度为 \(\mathcal{O}(m^2)\)，完全可以接受。
再回到答案的式子，此时它变为了：
\[Ans = a_0(1 + x)^n + \sum_{p = 1}^m a_p\sum_{i = 1}^p A_p(i) \times n^{\underline i} \times \sum_{k = i}^n\left[ x^k \times \binom{n - i}{k - i} \right] \]再把 \(\sum\limits_{k = i}^{n} x^k \times \dbinom{n - i}{k - i}\) 单独拿出来看，发现它变形可以用 二项式定理 转化：
\[\sum_{k = i}^{n} x^k \times \dbinom{n - i}{k - i} = x^i \sum_{k = 0}^{n - i} x^k \times \binom{n - i}k = x^i(1 + x)^{n - i} \]于是有：
\[Ans = a_0(1 + x)^n + \sum_{p = 1}^m a_p \sum_{i = 1}^p A_p(i) \times n^{\underline i} \times x^i(1 + x)^{n - i} \]时间复杂度 \(\mathcal O(m^2 \log n)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXM = 1e3 + 10;
int n, x, p, m, a[MAXM];
ll down[MAXM], s[MAXM][MAXM];
ll qp(ll base, int e) {
ll res = 1;
while (e) {
if (e & 1) res = res * base % p;
base = base * base % p;
e >>= 1;
}
return res;
}
int main() {
ios::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> x >> p >> m;
for (int i = 0; i <= m; i++) cin >> a[i];
down[1] = n, s[1][1] = 1;
for (int i = 2; i <= m; i++) down[i] = down[i - 1] * (n - i + 1) % p;
for (int i = 2; i <= m; i++) {
for (int j = 1; j <= i; j++) {
s[i][j] = (s[i - 1][j - 1] + j * s[i - 1][j]) % p;
}
}
ll ans = a[0] * qp(1 + x, n) % p;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= i; j++) ans = (ans + a[i] * s[i][j] % p * down[j] % p * qp(x, j) % p * qp(1 + x, n - j)) % p;
}
cout << ans;
return 0;
}