qwq..

一些定义

$ \Big \lbrace { n \atop k } \Big \rbrace $为第二类斯特林数，即把将一个有$n$件物品的集合划分为$k$个非空子集的方法数。

$ x^{\underline{y}} = \prod_{i=0}^{y-1}(x-i) $称作下降幂。

一些式子

$$ \Big \lbrace { n \atop k } \Big \rbrace = k \Big \lbrace { n - 1 \atop k } \Big \rbrace + \Big \lbrace { n - 1 \atop k - 1 } \Big \rbrace $$

递推式，考虑第$n$个元素所在的集合，可能自己一个集合，也可能和其他元素在一个集合。

$$ \Big \lbrace { n \atop k } \Big \rbrace = \frac{1}{k!} \sum_{i=0}^{k} (-1)^{k - i} {k \choose i} i^n $$

将一个有$n$件物品的集合划分为$k$个有标号可空子集的方法数为$k^n$，通过这个来容斥。

$$ x^k=\sum_{i=0}^{k}\Big \lbrace { k \atop i} \Big \rbrace x^{\underline{i}} $$

将一个有$k$件物品的集合划分为$x$个有标号可空子集的方法数为$x^k$，这也可以通过枚举有多少个子集是空的得到。

$$ (x+1)^{\underline{k+1}} - x^{\underline{k+1}} = (x + 1) x ^ {\underline{k}} - x ^ {\underline{k}} (x - k) = (k + 1) x^{\underline{k}} $$

$$ x^{\underline{k}} = \frac{(x+1)^{\underline{k+1}} - x^{\underline{k+1}}}{k + 1} $$

$$ \sum_{i=0}^{n}i^{\underline{k}} = \sum_{i=0}^{n}\frac{(i+1)^{\underline{k+1}} - i^{\underline{k+1}}}{k+1} = \frac{(n+1)^{\underline{k+1}}}{k + 1} $$

下降幂的前缀和。

自然数幂和

$$ \sum_{i=0}^{n} i^k = \sum_{i=0}^n \sum_{j=0}^{k} \Big \lbrace {k \atop j} \Big \rbrace i^{\underline{j}} $$

$$ =\sum_{j=0}^{k} \Big \lbrace {k \atop j} \Big \rbrace \sum_{i=0}^{n} i^{\underline{j}} $$

$$ =\sum_{j=0}^{k} \Big \lbrace {k \atop j} \Big \rbrace \frac{(n+1)^{\underline{j+1}}}{j+1} $$

然后直接计算这个式子，我们就得到了一个和$n$无关的计算方法。

题目链接

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3000, mod = 1000000007;
int t, k, s[maxn + 10][maxn + 10], inv[maxn + 10];
ll n;

int add(int x, int y) {
    x += y; return x < mod ? x : x - mod;
}
int dec(int x, int y) {
    x -= y; return x < 0 ? x + mod : x;
}
int mul(int x, int y) {
    return 1ll * x * y % mod;
}

void prework() {
    s[0][0] = 1;
    for (int i = 1; i <= maxn; ++i)
        for (int j = 1; j <= i; ++j)
            s[i][j] = add(mul(j, s[i - 1][j]), s[i - 1][j - 1]);
    for (int i = 1; i <= maxn; ++i)
        inv[i] = i == 1 ? 1 : dec(0, mul(mod / i, inv[mod % i]));
}

int main() {
    prework();
    scanf("%d", &t);
    while (t--) {
        scanf("%lld%d", &n, &k); int t = (n + 1) % mod, ans = 0;
        for (int i = 0; i <= k; ++i) {
            ans = add(ans, mul(s[k][i], mul(t, inv[i + 1])));
            t = mul(t, ((n - i) % mod + mod) % mod);
        }
        printf("%d\n", ans);
    }
}