「Codeforces 932E」Team Work【数论】

Time Limit: 2 Sec Memory Limit: 512 MB

Description

You have a team of NN people. For a particular task, you can pick any non-empty subset of people. The cost of having xx people for the task is xkx^k.

Output the sum of costs over all non-empty subsets of people.

Input

The only line of input contains two integers NN (1N1091 \leqslant N \leqslant 10^9) representing total number of people, and kk (1k50001 \leqslant k \leqslant 5000).

Output

Output the sum of costs for all non-empty subsets modulo 109+710^9+7.

Sample Input

1
2
3
4
5
Sample Input #1:
1 1

Sample Input #2:
3 2

Sample Output

1
2
3
4
5
Sample Output #1:
1

Sample Output #2:
24

Hint

There are seven non-empty subsets.

  • {1}\{1\} with cost 12=11^2 = 1
  • {2}\{2\} with cost 12=11^2 = 1
  • {1,2}\{1, 2\} with cost 22=42^2 = 4
  • {3}\{3\} with cost 12=11^2 = 1
  • {1,3}\{1, 3\} with cost 22=42^2 = 4
  • {2,3}\{2, 3\} with cost 22=42^2 = 4
  • {1,2,3}\{1, 2, 3\} with cost 32=93^2 = 9

The total cost is 1 + 1 + 4 + 1 + 4 + 4 + 9 = 24.

Solution

考虑 xkx^k 的意义,xkx^k 表示从 xx 人的集合中选择可重复的 kk 个人的组合的数量。对于每个子集计算所有的组合并求和即为答案。这显然计算了相同的结果。

假设有由不同的 ii 个人构成的大小为 kk 的组合。可以从哪些子集构造这个组合?显然这 ii 个人必须位于这个子集中。但对于其他的人有两个选择:在子集中或者不在。这并不影响答案,所以有 2ni2^{n-i} 个这样的子集。

dp(j,i)dp(j, i) 表示由不同的 ii 个人构成的大小为 jj 的组合的方案数,那么答案为

i=1min{n,k}(dp(k,i)2ni)\displaystyle \sum_{i=1}^{\min \{n, k\}} \Big(dp(k, i) \cdot 2^{n-i}\Big)

dp(j,i)dp(j, i) 可以很容易用动态规划求出,即

dp(j,i)=idp(j1,i)+(ni+1)dp(j1,i1)dp(j, i) = i \cdot dp(j-1, i) + (n-i+1) \cdot dp(j-1, i-1)

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxk = 5010, mod = 1e9 + 7;
ll n, k, ans, dp[maxk][maxk];

ll power(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}

int main() {
cin >> n >> k;
dp[0][0] = 1;
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= i; j++) {
dp[i][j] = (j * dp[i - 1][j] + (n - j + 1) * dp[i - 1][j - 1]) % mod;
}
}
for (int i = 1; i <= min(n, k); i++) {
ans = (ans + dp[k][i] * power(2, n - i)) % mod;
}
cout << ans << endl;
return 0;
}