「学习笔记」斯特林数

第一类斯特林数

第一类斯特林数 $s(n, m)$ 表示长度为 $n$ 的置换有 $m$ 个环的方案数。

第一类斯特林数有递推式 $s(n, m) = s(n - 1, m - 1) + s(n - 1, m) \times (n - 1)$，（讨论第 $n$ 个数新开一个环或者接在之前某个数后面），还有 $s(n, m) = \sum_{i = 1}^n s(n - i, m - 1) \times (i - 1)! \times C(n - 1, i - 1)$（枚举第一个数所在的环的大小，并考虑其他数的排法）。

可以用分治 FFT 在 $O(n \log^2 n)$ 的时间内求出第一类斯特林数的一行。

Count The Buildings

「HDU 4372」Count the Buildings

题目描述

求前缀递增单调栈长度为 $x$，后缀递增单调栈长度为 $y$ 的长度为 $n$ 的排列个数。

数据范围：$T \le 10^5, n, x, y \le 2000$。

思路分析

考虑排列中 $n$ 的位置，它左边形成了 $x - 1$ 组 $a_{l_i}, a_{l_i + 1}, \cdots, a_{r_i}$，其中 $l_i \le r_i, r_i + 1 = l_{i - 1}$，满足 $a_{l_i} > a_{l_i + 1}, a_{l_i + 2}, \cdots, a_{r_i}$，并且 $a_{l_{i}} < a_{l_{i + 1}}$。其实就是左边的置换有 $x - 1$ 个环的方案数（对于每个环把最大值转到第一位，并把环按照最大值排序），右边同理。问题变成了左边 $x - 1 + y - 1$ 个置换，选 $x - 1$ 个放左边的方案数，也就是 $s(n - 1, x + y - 2) \times C(x + y - 2, x - 1)$。

代码实现

#include <bits/stdc++.h>

第二类斯特林数

第二类斯特林数 $S(n, m)$ 表示 $n$ 个不同元素分成 $m$ 个集合的方案数。

第二类斯特林数有递推式 $S(n, m) = S(n - 1, m - 1) + S(n - 1,m) \times m$（枚举最后一个数新开一个集合或插入之前的一个集合），还有 $S(n, m) = \sum_{i = 1}^m S(n - i, m - 1) \times C(n - 1, i - 1)$（枚举第一个数所在集合的大小，然后考虑其他数的选法）。

有恒等式 $n^m = \sum_{i = 0}^{n} S(m, i) \times i! \times C(n, i) = \sum_{i = 0}^{n} S(m, i) \times n^{\underline{i}}$，这样可以把 $x^k$ 转化成下降幂的形式。

第二类斯特林数·行

「Luogu 5395」第二类斯特林数·行

题目描述

求 $S(n, 0), S(n, 1), \cdots, S(n, n)$。

数据范围：$n \le 2 \times 10^5$。

思路分析

前置知识——二项式反演：

$$F(n) = \sum_{i = 0}^{n} \binom{n}{i} \times G(i)$$ $$G(n) = \sum_{i = 0}^{n} (-1)^{n - i} \times \binom{n}{i} \times F(i)$$

那么，利用二项式反演，我们可以推出第二类斯特林数的通项公式：

$$n^m = \sum_{i = 0}^{n} S(m, i) \times i! \times C(n, i)$$ $$S(m, n) = \frac{1}{n!} \sum_{i = 0}^{n} i^m \times (-1)^{n - i} \times C(n, i)$$

当然这个式子也可以用容斥原理来解释。式子变形一下可得：

$$S(n, m) = \frac{1}{m!} \sum_{i = 0}^{m} (m - i)^n \times (-1)^{i} \times C(m, i)$$

可以把 $i$ 看作空集合的个数，我们把元素随意放在其他的集合中，然后进行容斥。最后由于盒子是相同的，答案要除以 $m!$。

构造多项式 $A_i = \sum_{i} \frac{i^n}{i!} x^i, B_i = \frac{(-1)^{i}}{(i)!} x_i$ 进行卷积即可求出 $S(n, 0), S(n, 1), \cdots, S(n, n)$。时间复杂度 $O(n \log n)$。

代码实现

#include <bits/stdc++.h>

Crash 的文明世界

「Luogu 4827」Crash 的文明世界

题目描述

给定 $n$ 个点的树，边权为 $1$，对于每个 $i$，求出 $\sum_{j = 1}^{n} \text{dist}(i, j)^k$。

数据范围：$n \le 5 \times 10^4, k \le 150$。

思路分析

首先我们有 $x^k = \sum_{i = 0}^{k} S(k, i) \times i! \times C(x, i)$，我们将 $\text{dist}(i, j)$ 代入其中，这样我们就只用求 $\sum_{j = 1}^{n} C(\text{dist}(i, j), k)$ 即可，而这个显然可以树形 dp 做。时间复杂度 $O(nk)$。

代码实现

#include <bits/stdc++.h>

求和

「BZOJ 4555」求和

题目描述

对于给定的 $n$，求：$f(n) = \sum_{i = 0}^{n} \sum_{j = 0}^{i} S(i, j) \times 2^j \times j!$，对 $998244353$ 取模。

数据范围：$n \le 10^5$。

思路分析

考虑 $g(n) = \sum_{i = 0}^{n} S(n, i) \times 2^i \times i!$ 的组合意义：将 $n$ 个元素放进若干个有序的集合，每个有元素的集合有两种状态。那么我们就有递推式：$g(n) = \sum_{i = 1}^{n} C(n, i) \times g(n - i) \times 2$，思路是枚举某个集合的大小。使用分治 FFT 计算即可，时间复杂度 $O(n \log^2 n)$。

代码实现

#include <bits/stdc++.h>

Partitions

「Codeforces 961G」Partitions

题目描述

给定 $n$ 个元素 $w_1, w_2, \cdots, w_n$，定义一个集合 $S$ 的权值为 $\vert S \vert \times \sum_{i \in S} w_i$，定义一个划分的权值为分出所有集合的权值和，求将这 $n$ 个元素划成 $k$ 个集合的权值和之和。

数据范围：$n, k \le 2 \times 10^5$。

思路分析

记 $W = \sum_{i = 1}^{n} w_i$，枚举某个点所在集合的大小可得答案等于：

$$W \times \sum_{i = 1}^{n} i \times C(n - 1, i - 1) \times S(n - i, k - 1)$$

那么我们开始推式子：

$$\begin{align*} & \sum_{i = 1}^{n} i \times C(n - 1, i - 1) \times S(n - i, k - 1) \\ = & \sum_{i = 1}^{n} i \times C(n - 1, i - 1) \times \sum_{j = 0}^{k - 1} \frac{(-1)^j \times (k - 1 - j)^{n - i}}{j! \times (k - 1 - j)!} \\ = & \sum_{j = 0}^{k - 1} \frac{(-1)^j}{j! \times (k - 1 - j)!} \sum_{i = 1}^{n} (k - 1 - j)^{n - i} \times i \times C(n - 1, i - 1) \\ = & \sum_{j = 0}^{k - 1} \frac{(-1)^j}{j! \times (k - 1 - j)!} \sum_{i = 1}^{n} \frac{(k - 1 - j)^{n - i} \times i \times (n - 1)!}{(i - 1)! \times (n - i)!} \\ = & \sum_{j = 0}^{k - 1} \frac{(-1)^j}{j! \times (k - 1 - j)!} \sum_{i = 1}^{n} \left[ \frac{(k - 1 - j)^{n - i} \times (n - 1)!}{(i - 1)! \times (n - i)!} + \frac{(k - 1 - j)^{n - i} \times (i - 1) \times (n - 1)!}{(i - 1)! \times (n - i)!} \right] \\ = & \sum_{j = 0}^{k - 1} \frac{(-1)^j}{j! \times (k - 1 - j)!} \sum_{i = 1}^{n} \left[ \frac{(k - 1 - j)^{n - i} \times (n - 1)!}{(i - 1)! \times (n - i)!} + \frac{(k - 1 - j)^{n - i} \times (n - 1)!}{(i - 2)! \times (n - i)!} \right] \\ = & \sum_{j = 0}^{k - 1} \frac{(-1)^j}{j! \times (k - 1 - j)!} \left[ \sum_{i = 1}^{n} (k - 1 - j)^{n - i} \times C(n - 1, i - 1) + (n - 1) \sum_{i = 1}^{n} (k - 1 - j)^{n - i} \times C(n - 2, i - 1) \right] \\ & \sum_{j = 0}^{k - 1} \frac{(-1)^j}{j! \times (k - 1 - j)!} \left[ (k - j)^{n - 1} + (n - 1) (k - j)^{n - 2} \right] \end{align*}$$

那么我们直接计算即可。

当然也有巧妙一点的方法：考虑某个元素对答案的贡献。首先每个元素都会贡献自己，贡献是 $w_i \times S(n, k)$；另外如果它和其他元素同在一个集合，我们让该集合中的每个其他元素都给它 $1$ 的贡献，也就是说我们可以先从剩下 $n - 1$ 个元素中选 $k$ 个集合，然后 $n - 1$ 个元素都给新加入的元素贡献 $1$，总贡献就是 $w_i \times (n - 1) \times S(n - 1, k)$。所以答案就是 $W \times \left[ S(n, k) + (n - 1) \times S(n - 1, k) \right]$，直接计算即可。时间复杂度 $O(n)$。

代码实现

#include <bits/stdc++.h>

异或图

题目描述

给定 $n$ 张 $m$ 个点的无向图，两个图的异或定义为邻接矩阵的异或，求所有 $2^n$ 个子集的图的异或和中有多少图是联通的。

数据范围：$n \le 60, m \le 10$。

思路分析

前置技能——斯特林反演（的变形？）：

$F(m) = \sum_{i = m}^{n} S(i, m) \times G(i)$

$G(m) = \sum_{i = m}^{n} (-1)^{i - m} \times s(i, m) \times F(i)$

我们考虑枚举全集的一个划分，强制划分出的任意两个集合之间不能有边（集合内部可以有边）。那么对于一个有 $m$ 个联通块的异或图，如果我们强制划出了 $n$ 个集合，这个方案会被计算 $S(m, n)$ 次。相当于如果我们强制划出 $i$ 个集合算出的方案数为 $F_i$，有 $i$ 个联通块的异或图共有 $G_i$ 个，那么 $F, G$ 就满足上面斯特林反演的关系。所以，我们先枚举划分，然后用线性基求出满足划分条件的异或图个数，从而求出 $F$ 数组，最后用斯特林反演求出 $G(1)$ 即可（注：$s(n, 1) = (n - 1)!$）。时间复杂度 $O(B(m) \cdot n \cdot \frac{m (m - 1)}{2})$，其中 $B(n) = \sum_{i = 0}^{n} S(n, i)$。

代码实现

#include <bits/stdc++.h>