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

标签：end limits 省选 题解 sum int 2020 Bmatrix binom

非常显然的，我们展开 \(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;
}

标签：end,limits,省选,题解,sum,int,2020,Bmatrix,binom
From： https://www.cnblogs.com/cqbzljh/p/17794335.html