CF932E Team Work

Posted on | Views:

第二类斯特林数.

给定 $n\le 10^9,k\le 5000$ ,求 $\sum_{i=0}^n \binom n i i^k$ ,答案对 $10^9+7$ 取模.

把后面的 $i^k$ 用第二类斯特林数展开成组合数的形式.
$$
\begin{aligned}
ans&=\sum_{i=0}^n \binom n i i^k \\
&=\sum_{i=0}^n \binom n i \sum_{j=1}^k {k\brace j} i^{\underline j} \\
&=\sum_{i=0}^n \binom n i \sum_{j=1}^k {k\brace j} \binom i j\cdot j! \\
&=\sum_{j=1}^k {k\brace j}\cdot j!\sum_{i=0}^n \binom n i\binom i j
\end{aligned}
$$
需要对 $\binom n i \binom i j$ 求和,考虑组合意义,可以看成每次从 $n$ 个数中选出若干个数,一共选了 $2$ 次, $2$ 次都被选中的有 $j$ 个.

那么我们可以先找出哪 $j$ 个数 $2$ 次都被选,其他数可以被选 $0$ 次,也可以被选 $1$ 次,得到 $\sum \binom n i \binom i j=2^{n-j}\binom n j$ .

代入得到
$$
ans=\sum_{j=1}^k {k\brace j}\cdot j!\cdot 2^{n-j}\binom n j
$$
$O(k^2)$ 预处理出所有的 $k\brace j$ 即可算出答案.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
const int P = 1e9 + 7;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
int fpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
const int N = 5e3 + 10;
int n, k, fac[N], s[N][N];
int main()
{
	n = read(), k = read();
	s[0][0] = 1;
	for (int i = 1; i <= k; ++i)
		for (int j = 1; j <= i; ++j)
			s[i][j] = add(s[i - 1][j - 1], mul(j, s[i - 1][j]));
	fac[0] = 1;
	for (int i = 1; i <= k; ++i)
		fac[i] = mul(fac[i - 1], i);
	int ans = 0, binom = n;
	for (int i = 1; i <= k && i <= n; ++i)
	{
		int tmp = mul(s[k][i], fac[i]);
		tmp = mul(tmp, mul(fpow(2, n - i), binom));
		inc(ans, tmp);
		binom = mul(binom, fpow(i + 1, P - 2));
		binom = mul(binom, n - i);
	}
	printf("%d\n", ans);
	return 0;
}