别人推公式用纸和笔,我推公式用 ( ext{typora})(确信
Description
求
[sum limits_{i=1}^{n} inom{n}{i} i^k
]
Solution
首先要知道一个经典的公式
[n^k = sum limits_{i=0}^{k} inom{n}{i} egin{Bmatrix} k \ i end{Bmatrix} i!
]
这个式子的组合意义:左边表示将 (k) 个有标号的球任意放入 (n) 个有标号的盒子里;右边则是组合数枚举有多少个空盒,然后将球放入非空的盒子里,最后由于盒子不同,还要乘上一个阶乘。
然后就可以大力推式子了
[sum limits_{i=1}^{n} inom{n}{i} i^k = sum limits_{i=1}^{n} inom{n}{i} sum limits_{j=0}^{k} inom{i}{j} egin{Bmatrix} k \ j end{Bmatrix} j! \= sum limits_{i=1}^{n} sum limits_{j=0}^{k} inom{n}{i} inom{i}{j} egin{Bmatrix} k \ j end{Bmatrix} j! \= sum limits_{i=1}^{n} sum limits_{j=0}^{k} inom{n}{j} inom{n-j}{i-j} egin{Bmatrix} k \ j end{Bmatrix} j! \= sum limits_{i=1}^{n} sum limits_{j=0}^{k} frac{n!}{j!(n-j)!} inom{n-j}{n-i} egin{Bmatrix} k \ j end{Bmatrix} j! \= sum limits_{i=1}^{n} sum limits_{j=0}^{k} frac{n!}{(n-j)!} inom{n-j}{n-i} egin{Bmatrix} k \ j end{Bmatrix} \= sum limits_{j=0}^{k} egin{Bmatrix} k \ j end{Bmatrix} frac{n!}{(n-j)!} sum limits_{i=1}^{n} inom{n-j}{n-i} \= sum limits_{j=0}^{k} egin{Bmatrix} k \ j end{Bmatrix} frac{n!}{(n-j)!} 2^{n-j}
]
然后就可以直接算了。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int _ = 5000 + 10;
ll N, K, S[_][_], ans;
inline void init() {
S[0][0] = 1;
for (int i = 1; i <= K; ++i)
for (int j = 1; j <= i; ++j)
S[i][j] = (S[i - 1][j - 1] + S[i - 1][j] * j % mod) % mod;
}
ll ksm(ll a, ll b) {
ll ret = 1;
for ( ; b; b >>= 1) {
if (b & 1) ret = ret * a % mod;
a = a * a % mod;
}
return ret;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("work.in", "r", stdin);
freopen("work.out", "w", stdout);
#endif
scanf("%lld%lld", &N, &K);
init();
ll _2 = ksm(2, N), inv = ksm(2, mod - 2), fac = 1;
for (int i = 0; i <= K; ++i) {
ans = (ans + fac * S[K][i] % mod * _2 % mod) % mod;
_2 = _2 * inv % mod;
fac = fac * (N - i) % mod;
}
printf("%lld
", ans);
return 0;
}