[省选联考 2020 A 卷] 组合数问题

题目描述

给定整数 $n$ , $x$ , $p$ ，一个 $m$ 次多项式 $f(k) = a_0 + a_1k + a_2k^2 + \cdots + a_mk^m$ ，计算

$$\left(\sum_{k=0}^{n}f(k)\times x^k\times \binom{n}{k}\right)\bmod p $$

$1\le n, x, p \le 10^9, 0\le a_i\le 10^9, 0\le m \le \min(n,1000)$ 。

题解

推式子

$$\begin{aligned} &\quad\sum_{k=0}^nf(k)x^k\binom{n}{k}\\ &=\sum_{k=0}^n\sum_{i=0}^ma_ik^ix^k\binom{n}{k}\\ &=\sum_{i=0}^ma_i\sum_{k=0}^nk^ix^k\binom{n}{k}\\ \end{aligned} $$

考虑生成函数

$$\begin{aligned} (1+x)^n&=\sum_{k=0}^nx^k\binom{n}{k}\\ ((1+x)^n)^{(i)}&=\sum_{k}x^k\binom{n}{k+i}(k+i)^{\underline{i}}\\ x^in^{\underline{n}}(1+x)^{n-i}&=\sum_kx^k\binom{n}{k}k^{\underline{i}} \end{aligned} $$

有结论

$$x^n=\sum_{k=0}^{n}\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline{k}} $$

代入

$$\begin{aligned} &\quad\sum_{i=0}^ma_i\sum_{k=0}^nk^ix^k\binom{n}{k}\\ &=\sum_{i=0}^ma_i\sum_{k=0}^{n}\sum_{j=0}^{i}\begin{Bmatrix}i\\j\end{Bmatrix}k^{\underline{j}}x^k\binom{n}{k}\\ &=\sum_{i=0}^ma_i\sum\limits_{j=0}^{i}\begin{Bmatrix}i\\j\end{Bmatrix}x^jn^{\underline{j}}(1+x)^{n-j} \end{aligned} $$

预处理斯特林数、特判 $a_0$ 。 $\mathcal{O}(m^2)$ 。

也有组合意义推法。

代码

const int N = 1010;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, x, mod, m;
	int a[N];
	int ans;
	int S[N][N];
	int add (int x, int y) { return x + y > mod? x + y - mod: x + y; }
	int dec (int x, int y) { return x - y < 0? x - y + mod: x - y; }
	int mul (int x, int y) { return 1ll * x * y % mod; }
	int qpow (int a, ll b) {
		int ans = 1;
		for (; b; b >>= 1, a = mul(a, a))
			if (b & 1) ans = mul(ans, a);
		return ans;
	}
	int main () {
		n = Read(), x = Read(), mod = Read(), m = Read();
		for (int i = 0; i <= m; i++) a[i] = Read();
		S[1][1] = 1;
		for (int i = 2; i <= m; i++)
			for (int j = 1; j <= i; j++)
				S[i][j] = add(mul(S[i - 1][j], j), S[i - 1][j - 1]);
		ans = mul(a[0], qpow((x + 1) % mod, n));
		for (int j = 1; j <= m; j++) {
			int pw = mul (qpow(x % mod, j), qpow((1 + x) % mod, n - j)), sum = 0;
			for (int i = 0; i < j; i++) pw = mul(pw, n - i);
			for (int i = j; i <= m; i++) sum = add(sum, mul(S[i][j], a[i]));
			ans = add(ans, mul(pw, sum));
		}
		printf ("%d\n", ans);
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}