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

tony102

2020 年 10 月 15 日

1504 次浏览

暂无评论

2092字数

题解

[Link](https://www.luogu.com.cn/problem/P6620)

一道题目=解锁$inf$知识点

## 前置知识

**下降幂**:

$$
n^{\underline k} = \binom{n}{k}*k!
$$

**二项式定理**：

$$
(x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{x-k}y^{k}
$$

并且我们注意到当$y=1$时，$(x+1)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} $

**第二类斯特林数**：$S(n,k) = S(n - 1,k-1) + k * S(n-1,k)$

**重要等式**

$$
\binom{n}{m} = \binom{n}{n - m}
$$

$$
x^k = \sum_{i=0}^{k} \binom{x}{i} * S(k,i) * i!
$$

解释：$x^k$相当于把$k$个小球放进$x$个盒子里（允许空盒），那么方案就是枚举不空的盒子个数 × 小球放进去的方案数 × 盒子标号不同（不懂就私聊

## Sol

解决完以上前置知识，我就花了小半小时（菜

看题目要我们解决的式子：

$$
\sum_{k = 0}^{n} f(k)*x^k*\binom{n}{k}
$$

$f(k)$是一个$m$次多项式，我们可以写成：

$$
\sum_{k=0}^{n} \sum_{i=0}^{m} a_{i} * k^{i}  * \binom{n}{k} * x^{k}
$$

把$k^i$用上面的恒等式替换

$$
\sum_{k=0}^{n} \sum_{i=0}^{m} a_{i} * \sum_{p=0}^{i} S(i,p) * \binom{k}{p} * p! * \binom{n}{k} * x^k
$$

观察到 $\binom{k}{p}$和$\binom{n}{k}$ 两项拆成阶乘形式：

$$
\frac{k!}{p!(k-p)!} * \frac{n!}{k!(n-k)!}
$$

同时消去$k!$，再同乘$\frac{(n-p)!}{(n-p)!} = 1$等式仍然成立：

$$
\frac{n! (n-p)!}{p!(n-p)!(n-k)!(n-p)!} = \binom{n}{p}*\binom{n-p}{k-p}
$$

所以此时式子变成了：

$$
\sum_{k=0}^{n} \sum_{i=0}^{m} a_{i} * \sum_{p=0}^{i} S(i,p) * \binom{n}{p} * \binom{n-p}{k-p} * p! * x^k
$$

我们将所有的求和限制提前，并且对每一项的顺序稍作改变：

$$
\sum_{k=0}^{n} \sum_{i=0}^{m} \sum_{p=0}^{i} \binom{n-p}{n-k} * x^k * a_i * S(i,p) * p! * \binom{n}{p}
$$

对二项式定理上面那个等式熟悉的话，我们感觉$\binom{n-p}{n-k}$和$x^k$可以合并。我们需要将$x$的指数稍作修改

$$
\sum_{k=0}^{n} \sum_{i=0}^{m} \sum_{p=0}^{i} \binom{n-p}{n-k} * x^{k-p} * x^p * a_i * S(i,p) * p! * \binom{n}{p}
$$

此时可以合并

$$
\sum_{i=0}^{m} \sum_{p=0}^{i} (x+1)^{n-p} * x^p * a_i * S(i,p) * p! * \binom{n}{p}
$$

至此，$(x+1)^{n-p}$和$x^p$两项均可通过快速幂计算，第二类斯特林数通过$O(m^2)$打表，$p!$和$\binom{n}{p}$可以一起计算

没了

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 1e3 + 5;

int n, x, p, m;
int a[SIZE], frac[SIZE], s[SIZE][SIZE];

inline int read()
{
	char ch = getchar();
	int f = 1, x = 0;
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
	return x * f;
}

inline int qPow(int a, int b)
{
	int ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return ans % p;
}

signed main()
{
	n = read(), x = read(), p = read(), m = read();
	for (int i = 0; i <= m; ++ i) a[i] = read();
	s[0][0] = 1;
	for (register int i = 1; i <= m; ++ i) {
		for (register int j = 1; j <= i; ++ j) 
			s[i][j] = (s[i - 1][j - 1] + 1ll * j * s[i - 1][j] % p) % p;
	}
	int ans = 0;
	for (register int i = 0; i <= m; ++ i) {
		frac[i] = qPow(x + 1, n - i);
		for (register int j = i - 1; j >= 0; -- j)
			frac[j] = frac[j + 1] * (x + 1) % p;
		for(register int j = 0, val1 = 1, val2 = 1; j <= i; ++ j, val1 = 1ll * val1 * (n - j + 1) % p, val2 = 1ll * val2 * x % p)
			ans = (ans + 1ll * a[i] * s[i][j] % p * val1 % p * val2 % p * frac[j] % p) % p;
	}
	printf("%lld\n", ans % p);
	return 0;
}
```

最后修改：2021 年 09 月 16 日