斯特林数 | mydcwfy's Blog

后面比较难理解，但是前面比较简单。

1. 第一类斯特林数

一）定义

是指将 $n$ 个不同的数划分成 $k$ 个圆排列的方案数，记作 $s(n,k)$ 或者 $n\brack m$。

二）求法

使用递推的方法。

第一种情况是 $n$ 专门放入 1 个圆排列，剩下的 $n-1$ 放入剩下的 $k-1$ 的圆排列中，这一类答案的贡献是 $s(n-1,k-1)$。

第二种情况是 $n$ 放入已有的 $k$ 个圆排列中。因为每一个数是不同的，所以可以发现，在一个圆排列中，可以放的位置（且不重复）恰好等于当前圆排列的大小。前面放的 $n-1$ 个数，所以有 $n-1$ 种方法，贡献为 $(n-1)\times s(n-1,k)$。

那么，我们就可以得到递推公式：

$s(n,k)=s(n-1,k-1)+(n-1)\times s(n-1,k)$

三）性质

$s(n,n)=1$：显然，每一个数放一个圆排列。
$s(n,1)=(n-1)!$：首先，不考虑旋转的话，就是 $n!$，但是每一种会对应 $n$ 种相同的，所以就是 $(n-1)!$。
$s(n, n-2) = 2\binom{n}{3}+3\binom{n}{4}$：其实都是一些简单的推导了。此处略去。
$\sum_{k=0}^ns(n,k)=n!$：这个需要用到第一类斯特林数的另一种表示方法，我们等一下再讲。

首先，我们定义一个 $x^{\bar n}=x(x+1)…(x+n-1)$，也就是上升幂。

定理：$x^{\bar{n}}=\sum_{k=0}^ns(n,k)x^k$。

证明：使用递推的方法，我们假设最后一个乘的是 $x$ 而不是 $n-1$，那么，对于 $x^k$ 的贡献就是剩下的 $x^{\overline{n-1}}$ 在 $x^{k-1}$ 的贡献。

如果最后乘的是 $n-1$，那么对于 $x^k$ 的贡献就是 $x^{\overline{n-1}}$ 在 $x^k$ 的贡献再乘上 $n-1$。

综上，我们发现和 $s(n,k)$ 的递推公式一模一样，所以定理得证。

接着，利用定理，我们令 $x=1$，那么可以化为：

$n!=\sum_{k=0}^ns(n,k)$

2. 第二类斯特林数

一）定义

是指将 $n$ 个不同的数划分 $k$ 个子集的方案数，记为 $S(n,k)$ 或 $n\brace m$。

二）求法

如果我们单独将 $n$ 放入一个集合，就是 $S(n-1,k-1)$。

如果我们将 $n$ 归入前面的 $k$ 个集合，就是 $k\times S(n-1,k)$。

于是，递推式就是：

$S(n,k)=S(n-1,k-1)+k\times S(n-1,k)$

3. 例题

T1：[FJOI2016]建筑师

题目传送门 Luogu

首先，一个显然的东西是：最高的肯定不会被挡住。

所以，我们可以将 $n$ 的位置枚举，然后左边可以看到 $A-1$ 个，右边可以看到 $B-1$ 个（均没有计算 $n$ 的贡献）。

然后，我们可以将这些可以看到的建筑以及它后面被挡住的分为一组。

可以在这一组中，因为最高的一定放在最前面。如果接在一起，可以看做一个圆排列，并且贡献就是 $1$。

这不就是第一类斯特林数吗！

我们就是将 $n-1$ 个放入 $A+B-2$ 个圆排列，贡献就是 ${n-1}\brack{A+B-2}$。

然后，我们要选择 $A-1$ 个放在前面，于是就是 ${A+B-2}\choose {A-1}$。

答案就是

${ {n - 1} \brack {A + B - 2} } \times { { A + B - 2} \choose {A - 1} }$

直接递推，时间复杂度为 $O(nk)$。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

typedef long long ll;
const int N = 5e4 + 10, K = 205, Mod = 1e9 + 7;
ll s[N][K], C[K][K];

void init()
{
    s[0][0] = 1;
    for (int i = 1; i < N; ++ i)
        for (int j = 1; j < K; ++ j)
            s[i][j] = (s[i - 1][j - 1] + (i - 1) * s[i - 1][j]) % Mod;
    C[0][0] = 1;
    for (int i = 1; i < K; ++ i)
        for (int j = 0; j < K; ++ j)
            if (!j) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % Mod;
}

int main()
{
    init();
    // cout << C[5][3] << ' ' << s[4][1] << endl;
    int t, n, a, b;
    cin >> t;
    while (t --)
    {
        scanf("%d %d %d", &n, &a, &b);
        printf("%lld\n", s[n - 1][a + b - 2] * C[a + b - 2][a - 1] % Mod);
    }
    return 0;
}

还有 Luogu 上的几道神仙题（一紫三黑），我们简单的讲一下。

T1：第二类斯特林数 · 行

题目传送门 Luogu

我们可以这样考虑：

${n \brace m} = \sum_{i=0}^m\dfrac{(-1)^i}{i!}\cdot \dfrac{(m-i)^n}{(m-i)!}$

发现可以先构造左边的 $f(x)=\sum_{i=0}^n \dfrac{(-1)^i}{i!},g(x)=\sum_{i=0}^n \dfrac{i^n}{i!}$，直接 NTT 卷积即可，就可以得到每一项 $h_m$ 所对应的项。

int main()
{
    init();
    int n;
    cin >> n;
    for (int i = 0; i <= n; ++ i) a[i] = qpow(i, n) * infact[i] % Mod;
    for (int i = 0; i <= n; ++ i) b[i] = (i & 1 ? Mod - infact[i] : infact[i]);
    int bit = 0;
    while (1 << bit < (n << 1)) bit ++;
    NTT(a, bit, 1), NTT(b, bit, 1);
    for (int i = 0; i < (1 << bit); ++ i) a[i] = a[i] * b[i] % Mod;
    NTT(a, bit, -1);
    for (int i = 0; i <= n; ++ i) printf("%lld ", a[i]);
    puts("");
    return 0;
}

T2：第二类斯特林数 · 列

题目传送门 Luogu

直接考虑指数型生成函数。

先看做 $n$ 个元素是相同的，$m$ 个盒子是不同的。

如果只有一个集合，用 $x^n$ 的系数表示方案数，那么就是：

$f(x)=\sum_{i=1}\dfrac{x^i}{i!}$

（注意指数型生成函数本身就要除以 $i!$，才能得到系数）

可以用 Taylor 展开式得到：$f(x)=e^x-1$（因为不是从 $i=0$ 开始的）。

那么，有 $m$ 个集合，就是 $g(x)=f(x)^k$，得到的系数再乘以一个 $i!$ 再除以 $m!$ 就可以得到答案了。

快速幂直接是 $g(x)=e^\left(k\ln f(x) \right)$。多项式 $\ln,\exp$ 结束了。注意第一项是 0，要整体向右平移 1 个单位，最后向左平移 $k$ 个单位。

int main()
{
    init();
    int n, k;
    cin >> n >> k;
    n ++;
    for (int i = 0; i < n - 1; ++ i) f[i] = infact[i + 1];
    static ll c[N];
    get_ln(a, c, len);
    int bit = 0;
    while ((1 << bit) < (len << 1)) bit ++;
    int tot = 1 << bit;
    for (int i = 0; i < tot; ++ i) c[i] = c[i] * k % Mod;
    get_exp(c, b, len);
    for (int i = n - 1; i >= k; -- i) g[i] = g[i - k];
    for (int i = 0; i < k; ++ i) g[i] = 0;
    for (int i = 0; i < n; ++ i) printf("%lld ", g[i] * fact[i] % Mod * infact[k] % Mod);

    return 0;
}

T3：第一类斯特林数 · 行

题目传送门 Luogu

首先，~~由题解~~可以得到：

$x^{\overline n} = \sum_{i=0}^{n}{n \brack i}x^i$

题目转化为求 $x^{\overline n}$ 的系数。

考虑倍增的算法。

已经得到了 $f(x)$，求 $f(x+c)$。

二项式定理就可以了。

$\begin{aligned} f(x+c)&=\sum_{i=0}^n[x^i]f(x)\sum_{j=0}^i {i \choose j}x^j c^{i-j} \\ &=\sum_{i=0}^n[x^i]f(x)\sum_{j=0}^i \dfrac{i!}{j!\cdot (i-j)!} x^j c^{i-j}\\ &=\sum_{j=0}^n \dfrac{x^j}{j!}\cdot \sum_{i=j}^n\dfrac{c^{i-j}}{(i-j)!}[x^i]f(x) i!\\ \end{aligned}$

很明显可以化为两个式子：$g(x)=\sum_{i=0}^n \dfrac{c^i}{i!}x^i,h(x)=[x^i]f(x)i!x^i$，发现就是次数相减。

将 $h(x)$ 翻转为 $[x^i]f(x)i! x^{n-i}$，那么就是次数相加了，变为 NTT 就可以了。

回归本题。

$x^{\overline {2n}} = x^{\overline n}\cdot (x+n)^{\overline{n}}$

先将 $x^\overline n$ 求出来，然后上面的式子（可以叫多项式平移）推出 $(x+n)^\overline n$，NTT 一下就是了。

注意 $n$ 为奇数的时候，可以直接暴力求 $x^\overline {n-1}\cdot (x+n)$ 即可。

void get_sti(int n, ll *a)
{
	if (n < 0) return;
	if (n == 0)
	{
		a[0] = 1;
		return;
	}
	static ll c[N], d[N], t[N];
	if (n & 1)
	{
		get_sti(n - 1, a);
		c[0] = 0;
		for (int i = 0; i < n; ++ i) c[i + 1] = a[i];
		for (int i = 0; i < n; ++ i) c[i] = (c[i] + a[i] * (n - 1) % Mod) % Mod;
		for (int i = 0; i <= n; ++ i) a[i] = c[i];
		// cout << n << endl;
		// for (int i = 0; i <= n; ++ i) cout << a[i] << ' ';
		// puts("");
		return;
	}
	get_sti(n >> 1, a);
	int m = n >> 1, bit = 0;
	while ((1 << bit) < n + 1) bit ++;
	int tot = 1 << bit;
	ll now = 1;
	for (int i = 0; i <= m; ++ i) c[m - i] = a[i] * fact[i] % Mod;
	for (int i = 0; i <= m; ++ i, now = now * m % Mod) d[i] = now * infact[i] % Mod;
	for (int i = m + 1; i < tot; ++ i) c[i] = d[i] = 0;
	// for (int i = 0; i <= m; ++ i) cout << c[i] << " \n"[i == m];
	// for (int i = 0; i <= m; ++ i) cout << d[i] << " \n"[i == m];
	NTT(c, bit, 1), NTT(d, bit, 1);
	for (int i = 0; i < tot; ++ i) c[i] = c[i] * d[i] % Mod;
	NTT(c, bit, -1);
	for (int i = 0; i <= m; ++ i) t[i] = c[m - i] * infact[i] % Mod;
	for (int i = m + 1; i < tot; ++ i) t[i] = 0;
	// for (int i = 0; i <= m; ++ i) cout << t[i] << " \n"[i == m];
	NTT(a, bit, 1), NTT(t, bit, 1);
	for (int i = 0; i < tot; ++ i) a[i] = a[i] * t[i] % Mod;
	NTT(a, bit, -1);
	for (int i = n + 1; i < tot; ++ i) a[i] = 0;
	// cout << n << endl;
	// for (int i = 0; i <= n; ++ i) cout << a[i] << ' ';
	// puts("");
}

T4：第一类斯特林数 · 列

题目传送门 Luogu

和 T2 差不多。

考虑只有一个集合的时候，就是：

$f(x)=\sum_{i=1}(i-1)!\dfrac{x^i}{i!}$

那么答案就是 $g(x) = f(x)^m$，最后答案乘上 $\dfrac{i!}{m!}$ 就可以了。

仍然注意第一项为 $0$，所以要先右移一位，做完后，再左移 $m$ 位。

int main()
{
    init();
    cin >> n >> k;
    n ++;
    for (int i = 0; i < n - 1; ++ i) a[i] = qpow(i + 1, Mod - 2);
    get_qpow(a, b, n - 1, k);
    for (int i = n - 1; i >= k; -- i) b[i] = b[i - k];
    for (int i = 0; i < k; ++ i) b[i] = 0;
    for (int i = 0; i < n; ++ i)
        printf("%lld ", b[i] * infact[k] % Mod * fact[i] % Mod);
    return 0;
}