题面
题解
我们知道有
[n^k = sum_{i = 0}^{n}i!inom{n}{i}egin{Bmatrix}k\iend{Bmatrix}
]
所以有
[displaystyleegin{aligned}sum_{i = 1}^{n}inom{n}{i}i^k&=sum_{i=0}^{n}inom{n}{i}i^k-egin{bmatrix}k=0end{bmatrix}\&= sum_{i = 0}^{n}inom{n}{i}sum_{j=0}^{i}j!inom{i}{j}egin{Bmatrix}k\jend{Bmatrix}-egin{bmatrix}k=0end{bmatrix}\&=sum_{i = 0}^{n}sum_{j=0}^{i}j!egin{Bmatrix}k\jend{Bmatrix}inom{n}{i}inom{i}{j}-egin{bmatrix}k=0end{bmatrix}end{aligned}
]
交换求和号
[displaystyle=sum_{j=0}^{min(n, k)}j!egin{Bmatrix}k\jend{Bmatrix}sum_{i=j}^{n}inom{n}{i}inom{i}{j}
]
因为 (i < j) 时, (inom{i}{j} = 0)
[displaystyle=sum_{j=0}^{min(n, k)}j!egin{Bmatrix}k\jend{Bmatrix}sum_{i=0}^{n}inom{n}{i}inom{i}{j}-egin{bmatrix}k=0end{bmatrix}
]
看到
[displaystylesum_{i=0}^ninom{n}{i}inom{i}{j}
]
它的组合意义是, 从 (n) 个白色的球中选出 (i) 个数染成黑色, 再从 (i) 个黑球中选 (j) 个染成红色
因为有一个 (sum_{i=0}^n) 所以最后的黑球个数可能是 (egin{bmatrix}0, n-jend{bmatrix})
所以就相当于从 (n) 个白球中选 (j) 个染成红色, 其他的随便染不染都行
所以有
[displaystylesum_{i = 0}^ninom{n}{i}inom{i}{j}=inom{n}{j}*2^{n-j}
]
代入得
[displaystyle=sum_{j=0}^{min(n, k)}j!egin{Bmatrix}k\jend{Bmatrix}inom{n}{j}*2^{n-j}-egin{bmatrix}k=0end{bmatrix}
]
预处理斯特林数和组合数即可
Code
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 5005;
const int mod = 1e9 + 7;
using namespace std;
int n, k, s[N][N], ans;
template < typename T >
inline T read()
{
T x = 0, w = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * w;
}
int fpow(int x, int y)
{
int res = 1;
for( ; y; y >>= 1, x = 1ll * x * x % mod)
if(y & 1) res = 1ll * res * x % mod;
return res;
}
int main()
{
n = read <int> (), k = read <int> ();
s[0][0] = 1;
for(int i = 1; i <= k; i++)
for(int j = 0; j <= i; j++)
s[i][j] = (!j ? 0 : (s[i - 1][j - 1] + 1ll * j * s[i - 1][j] % mod) % mod);
for(int res, j = 0; j <= k; j++)
{
if(j > n) break;
res = 1;
for(int i = n; i > n - j; i--)
res = 1ll * res * i % mod;
ans = (ans + 1ll * s[k][j] * res % mod * fpow(2, n - j) % mod) % mod;
}
if(!k) ans--;
printf("%d
", ans);
return 0;
}