文章总览：落井当下石

这篇文章讲的内容是斯特林数和卡特兰数，两个非常常用的计数类型数列，初赛常考（好吧我怎么感觉斯特林数我从来没有见到过）

本文内容限定如下：

  1. 第一类斯特林数推导及实现
  2. 第二类斯特林数推导及实现
  3. 斯特林数例题
  4. 卡特兰数推导及应用
  5. 卡特兰数例题

算法其一：得胜必追击

第一类斯特林数

第一类斯特林数就是：将 $n$ 个不同物体排成 $k$ 个互不区分的非空圆排列的方案数。

可以简单的分来讨论，对于第一类斯特林数 $S1(n,k)$：

  1. 对于第 $n$ 个数新开了一个圆排列，方案数为 $S1(n-1,k-1)$。
  2. 对于第 $n$ 个数插入了以前某一个圆排列，方案数为 $(n-1)\times S1(n-1,k)$，因为在插入这个数以前，一共有 $n-1$ 个数，由于是圆排列，环上的空位数量还是 $n-1$ 个，所以乘起来。

边界条件也是非常的明显是 dp[0][0]=1 。

1
2
3
4
5
6
dp[0][0] = 1;
for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= i; j++) {
        dp[i][j] = (n-1) * dp[i-1][j] + dp[i-1][j-1];
    }
}

第二类斯特林数

第二类斯特林数就是：将 $n$ 个不同物体分成 $k$ 个集合的方案数。

和第一类斯特林数一样的：

  1. 对于第 $n$ 个元素单独开一个集合：$S2(n-1,k-1)$。
  2. 对于第 $n$ 个元素插入前面的某一个集合，由于集合是无序的：$k\times S2(n-1,k)$。

可以写出下面的代码：

1
2
3
4
5
6
dp[1][1] = 1;
for(int i = 2; i <= n; i++) {
    for(int j = 1; j <= i; j++) {
        dp[i][j] = j * dp[i-1][j] + dp[i-1][j-1];
    }
}

例题其一：我就是这样

  • 斯特林数例题

第一类斯特林数例题

HDU4372 - Counting the Buildings

在一排中，有 $N$ 个高楼沿直线排列，编号从 $1$ 到 $N$。所有高楼的高度都不同，并且在 $1$ 到 $N$ 之间。当您站在第一个高楼的前面并向前看时，可以看到 $F$ 个高楼。当您位于最后一个高楼后面并向后看时，可以看到 $B$ 个高楼。如果高楼比您和它之间的任何高楼都高，则可以看到该高楼。

现在，给定 $N,F,B$，您的任务是弄清存在多少种这样序列的高楼。

这道题的话，我们可以简单的画一下每一个楼房的情况，这里以 $N=7,F=3,B=2$ 举例。

题目示例

我们把最高的楼看前面和后面能看见的楼房的分界线。每一个能看见的楼房之间分组，被记入能看到楼房的楼房是这一组的牢大，其余的算是小弟。除了最高的高楼单独算一组以外，其他的组数总共应该是 $F+B-2$ 个小组。

那么从这些小组里面取出 $F-1$ 个放在前面，并且一旦选出来，这个顺序一定是确定的，不然你无法保证可以看到包括最高楼在内的 $F$ 个不同高度的楼房；而且前面的房子选出来以后，后面的小组顺序也就自然而然地确定了。用组合数表示出来就是 C(F+B-2, F-1) 种方法。

然后我们来考虑如何分组，把 $n$ 个互不相同的楼房放到 $F+B-2$ 个小组里面，经典的第一类斯特林数，直接用刚刚说的做法即可。

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

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int P = 1000000007;

int n, F, B;
ll dp[2010][2010], C[2010][2010];

void Init() {
    dp[0][0] = 1;
    C[0][0] = 1;
    for(int i = 1; i <= 2000; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            dp[i][j] = (dp[i - 1][j - 1] + (i-1ll) * dp[i - 1][j] % P) % P;
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % P;
        }
    }
}

int main() {
    Init();
    int T = read();
    while(T--) {
        read(n, F, B);
        if(F + B - 1 > n || max(F, B) <= 1) {
            printf("0\n");
            continue;
        }
        ll ans = dp[n - 1][F + B - 2] * C[F + B - 2][F - 1] % P;
        printf("%lld\n", ans);
    }
    return 0;
}

第二类斯特林数例题

第二类斯特林数没有找到例题……我讲一些常见应用罢（绝对不是懒得找

最基础的应用，就是放球问题。

放球问题　其一

有 $n$ 个不同的球，放到 $m$ 个相同的盒子里，盒子不允许有空的。

这就是非常明显的第二类斯特林数的定义，直接套模板就可以了，这个没什么好说的，另外如果盒子不相同，我们就只需要多乘上 $m!$ 种方案作为没一个盒子的排列即可。

好像关于斯特林数的更多应用是一种被称为斯特林数展开的东西（我不会，逃

算法其二：打人要打脸

  • 卡特兰数推导及应用

卡特兰数推导

接下来的内容是属于卡特兰数的。

卡特兰数大概是这样的内容：在一个 $n\times n$ 的网格中，从左下角的 $A$ 点走到右上角的 $B$ 点，只能往右或者往上走，但是路径始终都不超过这个网格的对角线的方案有多少种（可以压线）

那么简单的绘制一下图形，这是计算推导卡特兰数的关键所在：

卡特兰数图像化示例

我们发现如果直接计算这样的卡特兰数很难，但是如果是换一个思路，我们从总体里面减去非法的，就有一点头绪了。显然的在这个路径上，我们会走 $2n$ 条边，因为只能往右往上来到点 $(n,n)$，所以最终一定会走 $n$ 条右边和 $n$ 条左边的路径，普通路径的方法数就应该是 $C_{2n}^n$。

接下来考虑非法方案。其实就是刚刚放的那张图的内容了，我们把绿色的 $n\times n$ 网格拓展到黄色部分，并做出蓝色对角线向上平移一格后的直线，显然的，对于一个非法的方案，他一定会触碰甚至越过了红线，这时候把这个路径对称过去，得到紫色的路径，不难发现 $B(n,n)$ 的对应点应该是 $(n+1,n-1)$。

非常显然的，在这个 $(n+1)(n-1)$ 的矩阵里，任意一个从 $A$ 到 $(n+1,n-1)$ 的普通路径，都可以被红线对称成一条从 $A$ 到 $(n,n)$ 的非法路线。因为一旦要从 $A$ 到达 $(n+1,n-1)$ 一定是要跨越红线的，既然跨越了红线，被红线对称过去就一定是跨越蓝线的，并且这个路径与对称后的路径显然是一一对应的。

那么答案就出来了，卡特兰数的计算公式就是：

卡特兰数应用

说到卡特兰数的应用，我们首先需要知道关于卡特兰数公式的变式：

  • $\operatorname{Cat}(n)=\cfrac{1}{n+1}\sum\limits_{i=0}^n\binom{n}{i}^2$

证明：

关于此式证明详见：【算法介绍】排列组合问题汇总 - 组合数的变形 | 祝馀宫

  • $\operatorname{Cat}(n+1)=\sum\limits_{i=0}^n\operatorname{Cat}(i)\operatorname{Cat}(n-i)$

证明：

理性证明很难，我们感性证明一下：

如果我们把卡特兰数定义中的向右走定义为左括号，向上走定义为右括号，因为被对角线限制，所以向上走的步数一定小于等于向右走的步数，并且在到达终点的时候向上和向右走的步数就是相等的。所以按照刚刚的构造方式，合法路径构成的一定是一个合法的括号序列，并且其中包含了 $n$ 对括号。

那么这时候我们可以赋予卡特兰数 $\operatorname{Cat}(k)$ 实际意义：$k$ 对括号的所有合法组合方法数。

那么这个式子就不难理解了，我们把 $n+1$ 对括号的组合分为两部分，前面一段，后面一段，当然这些部分的长度也是可以为 $0$ 的，然后把前面一段套上一个括号，前面和后面总共花费的括号数量是 $n$ 个，那么多套了一个括号就是 $n+1$ 个括号了。并且因为公式中 $i$ 和 $n-i$ 的对称性，是不会遗漏方案的。

这样就是感性的证明了这一个变式。

  • $\operatorname{Cat}(n+1)=\cfrac{2(2n+1)}{n+2}\operatorname{Cat}(n)$

证明：

显然的这样就结束了。

卡特兰数的应用有很多，比较常见的有下面几种：

  1. $n$ 对括号合法匹配方案数

    解释：这个刚刚在上面的第二个变式证明中说过了。

  2. $n$ 个节点二叉树的形态数

    解释：众所周知，一棵树可以写出欧拉序或者 DFS 序的形式，我们把第一次进入某一个节点看作左括号，最后一次离开某一个节点看作右括号，这样每个节点对应一对括号，就变成上面的第一个应用了。

  3. $n+1$ 个叶子（ $n$ 个非叶子节点）的满二叉树的形态数。

    解释：一棵有 $n$ 个节点的普通二叉树的总指针数（即可以承载的最大父子关系数量）应该是每个节点 $2$ 个即 $2n$ 个空指针，当然这个结论的前提是我们把叶子节点也当作有两个可支配指针不过一个都没有使用。已经使用了的指针数量就是这个树的边数即 $n-1$，显然剩余指针数量为 $2n-(n-1)=n+1$ 刚刚好就是题目要求补齐的节点数量，由于父子关系唯一，一个指针就代表了一个新的节点，这显然是一一对应的关系。

  4. $n$ 个数出入栈的排列总数

    解释：同样的，入栈左括号出栈右括号，入栈的操作次数应该永远大于等于出栈操作次数，并且每一个数只会出入栈一次，所以最终问题还是转化为应用一。

  5. 对 $n+2$ 边的凸多边形进行不同的三角形分割的方案数，分割线只能在断点处相交。

    解释：和变式二中我们的感性证明是类似的，如果我们选用一条边作为分割把两边分成子问题，显然是可行的，问题转化，自然的就用变式二的计算方式看出是对的了。

例题其二：骂人不留口

  • 卡特兰数例题

题目大意

题目传送门：HDU5184 - Brackets

以下是“规则的方括号”序列的定义：

  1. 空序列是常规方括号序列，
  2. 如果 $s$ 是规则括号序列，则 $(s)$ 是规则括号序列
  3. 如果 $a$ 和 $b$ 是规则括号序列，则 $ab$ 是规则括号序列。
  4. 没有其他的序列是一个常规方括号序列

例如，以下所有字符序列都是常规括号序列：()，(())，()()，()(())

而以下字符序列不是：(，)，)(，(()，((()

现在我们要构造一个长度为 $n$ 的常规括号序列，当已经给出前几个括号时，我们可以得到多少个常规括号序列。

解题思路

注意到给出的是前缀，所以相当于卡特兰数定义上规定了一段路，看我们接下来走什么。首先可以明确一点，如果给出的前缀已经违规，最后的结果一定是 $0$。然后其他的也很简单，总计走 $n$ 步，确定了前 $len$ 步，并且已经有了 $a$ 步往右，直接套用上面推导卡特兰数的思路一推，答案即为：

正确代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int P = 1e9 + 7;

int n;
char s[1000010];

ll fact[1000010];
ll inv[1000010];

inline ll Pow(ll a, int b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return ans;
}

inline void Init() {
    fact[0] = 1, inv[0] = Pow(1, P - 2);
    for(int i = 1; i <= 1000000; i++) {
        fact[i] = fact[i - 1] * i;
        fact[i] %= P;
        inv[i] = Pow(fact[i], P - 2);
    }
}

inline ll C(int n, int m) {
    if(n < m) return 0;
    if(n == 0 || n == m) return 1;
    return 1LL * fact[n] * inv[m] % P * inv[n - m] % P;
}

inline void Work() {
    if(n % 2 == 1) {
        printf("0\n");
        return ;
    }
    int cntl = 0, cntr = 0, len = strlen(s);
    for(int i = 0; i < len; i++) {
        if(s[i] == '(') cntl++;
        else cntr++;
        if(cntl < cntr) {
            printf("0\n");
            return ;
        }
    }
    printf("%lld\n", (C(n - len, n / 2 - cntl) - C(n - len, n / 2 - cntl - 1) + P) % P);
}

int main() {
    Init();
    while(~scanf("%d%s", &n, s)) {
        Work();
    }
    return 0;
}

算法实战：没人能负我

查看相关算法标签喵！

参考资料（以下排名不分先后）