「联合省选 2020 A」组合数问题

之前以为是我不会的科技题，没想到是勾巴题（（

观察到多项式次数 $m\le 1e3$，考虑计算每项的贡献：

$$\sum\limits_{i=0}^m a_i\sum\limits_{k=0}^n k^i x^k \dbinom n k$$

将 $k^i$ 用第二类斯特林数换掉：

$$\sum\limits_{i=0}^m a_i\sum\limits_{k=0}^nx^k\dbinom n k\sum\limits_{j=0}^{\min(k,i)}\dbinom k j\begin{Bmatrix}i\\j\end{Bmatrix}j!$$

然后推一下柿子：

$$\begin{aligned}\sum\limits_{i=0}^m a_i\sum\limits_{k=0}^nx^k\dbinom n k\sum\limits_{j=0}^{\min(k,i)}\dbinom k j\begin{Bmatrix}i\\j\end{Bmatrix}j!&=\sum\limits_{i=0}^m\sum\limits_{j=0}^ia_i\begin{Bmatrix}i\\j\end{Bmatrix}j!\sum\limits_{k=j}^nx^k\dbinom n k\dbinom k j\\ &=\sum\limits_{i=0}^m\sum\limits_{j=0}^ia_i\begin{Bmatrix}i\\j\end{Bmatrix}j!\sum\limits_{k=j}^nx^k\dbinom{n}{j}\dbinom{n-j}{k-j}\\ &=\sum\limits_{i=0}^m\sum\limits_{j=0}^ia_i\begin{Bmatrix}i\\j\end{Bmatrix}j!\dbinom n j x^j\sum\limits_{k=0}^{n-j}\dbinom{n-j}{k}x^k\\ &=\sum\limits_{i=0}^m\sum\limits_{j=0}^ia_i\begin{Bmatrix}i\\j\end{Bmatrix}j!\dbinom n j x^j(x+1)^{n-j}\end{aligned}$$

然后直接算就完了，时间复杂度 $\mathrm{O(m^2)}$。

$\texttt{Code:}$

#include <bits/stdc++.h>
using namespace std;
int cmd;
inline int add(int a, int b) {a += b; return a < cmd ? a : a - cmd;}
inline int sub(int a, int b) {a -= b; return a < 0 ? a + cmd : a;}
inline int mul(int a, int b) {return 1ll * a * b % cmd;}
int fpow(int a, int b) {
	int res = 1;
	for (; b; b >>= 1, a = mul(a, a))
		if (b & 1) res = mul(res, a);
	return res;
}
const int maxn = 1e3 + 5;
int n, x, m, ans, S2[maxn][maxn], pw[maxn];
int main() {
	scanf("%d%d%d%d", &n, &x, &cmd, &m);
	S2[0][0] = S2[1][1] = 1;
	for (int i = 2; i <= m; i++)
	for (int j = 1; j <= i; j++) S2[i][j] = add(S2[i - 1][j - 1], mul(S2[i - 1][j], j));
	for (int i = 0; i <= m; i++) pw[i] = fpow(x + 1, n - i);
	for (int i = 0; i <= m; i++) {
		int a; scanf("%d", &a);
		int p = 1;
		for (int j = 0; j <= min(i, n); p = mul(p, mul(x, n - j)), j++)
			ans = add(ans, mul(a, mul(S2[i][j], mul(p, pw[j]))));
	}
	printf("%d", ans);
	return 0;
}