「草稿」组合计数综合练习

常见数列

贝尔数：n 个数分成若干个非空集合的方案数

$B_{n} = \sum_{k = 0}^{n} S (n, k)$ 。
递推： $B_{n} = \sum_{k = 0}^{n - 1} (k n - 1) B_{k}$ 。

调和级数： $H_{n} = \sum_{i = 1}^{n} \frac{1}{i} = ln n + ε_{n} + γ$ ，其中 $γ$ 是欧拉常数， $ε_{n} \approx \frac{1}{2 n}$ 。

容斥原理

ARC 102 E

有 n 个不可取分的 k 面骰子，对于每个 $i = 2, 3, \dots, 2 K$ ，求有多少种方案使得：任意两个骰子朝上的面要么相同，要么和不为 $i$ 。答案对 $998244353$ 取模。
$2 \leq n \leq 2000, 1 \leq k \leq 2000$ 。

先枚举 $i$ 。也就是说 $1, i - 1$ ， $2, i - 2$ ，……不能同时出现。那么就出现 0 次或者一次。直接枚举有多少组里出现了一个。假设有 $j$ 组。设这 $j$ 个有 $2^{j}$ 种选择（左边或者右边）。然后考虑出现了多少次： $x_{1} + x_{2} + \dots + x_{j}$ ，其中 $x_{i} > 0$ 。然后枚举 $y_{i}$ 表示比 $i$ 大的数字出现的次数。把 $x, y$ 放在一起插版即可。

集训队作业 2018 小 z 的礼物

设 $t_{x}$ 表示 x 这个礼物第一次得到的时间。要求 $E (max t_{x})$ 。考虑容斥。

T \in S \sum (- 1)^{∣ T ∣ + 1} E (x \in T min t_{x})

$T$ 定下来：直接算随到一个的概率。假设有 $X$ 个 pair 满足，一共有 $Y$ 个 pair。那么期望就是 $E (min T) = \frac{Y}{X}$ 。

考虑 DP。 $f (i, j, S, x)$ 表示现在考虑第 $i$ 行第 $j$ 个格子， $S$ 表示每行最后一个元素选不选。考虑 $x$ 是否在子集中。

ARC 96 E Everything on It

题意：求有多少个子集族满足：

其中任意一个子集都是 $[n]$ 的子集；
任意两个子集不同；
$1, 2, \dots, n$ 都在其中出现至少两次。

考虑容斥。枚举 $i$ 表示 $1, 2, \dots, i$ 出现次数小于等于 $1$ 。那么答案为

i \sum (i n) (- 1)^{i} F (i)

其中 $F (i)$ 表示 $1, \dots i$ 出现次数小于等于 1 的方案数。

考虑枚举有 $k$ 个集合含有 $[1, i]$ 中至少一个，其他集合则不含有 $[1, i]$ 。

显然不含有 $[1, i]$ 的子集族数为 $2^{2^{n - i}}$ 。

对于这个 $k$ 个集合，我们考虑把 $1, \dots, i$ 分入 $k$ 个集合，有的数字可以不放，每个数字最多出现一次。相当于再拿一个集合出来装垃圾。我们给垃圾堆强制加入数字 $0$ 来保证每个集合非空。同时我们认为 $0$ 所在的集合指向垃圾堆。这样就相当于是 $i + 1$ 个数分成 $k + 1$ 个非空集合，那么方案数就是 $S (i + 1, k + 1)$ 。

至于这 $k$ 个集合的其他数字则可以任意填，并且由于 $k$ 个集合各种含有不同的 $1, \dots, i$ 的数字，因此其他部分就不需要考虑重复的问题了，那么方案数就是 $(2^{n - i})^{k}$ 。

因此得到

F (i) = 2^{2^{n - i}} k \sum (2^{n - i})^{k} S (i + 1, k + 1)

ARC 101 E Ribbons on Tree

题意：给你一个 n 个点的数，其中 n 是偶数。问有多少种将 $n$ 个点配成 $n /2$ 对的方式，使得每对点的路径并覆盖了整棵树。 $n \leq 5000$ 。

不合法的情况就是某条边不被经过，相当于这条边被割掉。因此考虑容斥。暴力的做法是枚举被割掉的边集，然后每个连通块内无限制连边的方案数，复杂度 $O (2^{n})$ 。

首先考虑无限制连边的方案数。对于一个大小为 $x$ 的连通块，它的配对方案数是

g (x) = {(x - 1) (x - 3) \dots 1 0 x \equiv 0 mod 2 x \equiv 1 mod 2

那么考虑 DP 计算容斥贡献。设 $f (i, j, 0/1)$ 表示 $i$ 的子树中， $i$ 所在连通块大小为 $j$ ，被割的边数的奇偶性为 $x$ 的配对方案数。注意，我们只统计被割掉的连通块的配对方案数， $i$ 所在的连通块暂不统计配对方案数。

假设 $1$ 是根，我们要求的答案显然是

i = 1 \sum n g (i) (f (1, i, 0) - f (1, i, 1))

考虑转移，对于 $(u \to v)$ 的边：

不割。相当于把 $v$ 所在的连通块接在 $u$ 所在的连通块上。则 $f (u, i)$ 和 $f (v, j)$ 可以贡献到 $f^{'} (u, i + j)$ 上。
割。则 $f (u, i)$ 和 $f (v, j) g (j)$ 贡献到 $f^{'} (u, i)$ 上。

对子树大小取 min，时间复杂度 $O (n^{2})$ 。

ARC 93 F

枚举 ${G_{1}, G_{2}, \dots, g_{n}}$ 的子集。要求 $S$ 中的所有集合都满足最小值在 $A$ 中，问方案数。记作 $f (S)$ 。答案就是 $\sum_{S} (- 1)^{∣ S ∣} f (S)$ 。

从大到小考虑 A 中的元素。 $d p (T)$ 表示 $T$ 的最小值属于 A。

斯特林反演

下降幂： $n^{\underline{m}} = \prod_{i = 0}^{m - 1} (n - i)$ 。

通常幂转下降幂： $x^{n} = \sum_{k = 0}^{n} S (n, k) x^{\underline{k}}$ 。

上升幂： $n^{\overline{m}} = \prod_{i = 0}^{m - 1} (n + i)$ 。

上升幂转通常幂： $x^{\overline{n}} = \sum_{k = 0}^{n} s (n, k) x^{k}$ 。

反演公式

斯特林反演：

f (n) = k = 0 \sum n S (n, k) g (k) g (n) = k = 0 \sum n (- 1)^{n - k} s (n, k) f (k)

反转公式

k = m \sum n (- 1)^{n - k} s (n, k) S (k, m) = [m = n] k = m \sum n (- 1)^{n - k} S (n, k) s (k, m) = [m = n]

引理：

x^{\underline{n}} = (- 1)^{n} (- x)^{\overline{n}} x^{\overline{n}} = (- 1)^{n} (- x)^{\underline{n}}

证明显然。

证明反转公式：

n^{m} = k = 0 \sum m S (m, k) n^{\underline{k}} = k = 0 \sum m S (m, k) (- 1)^{k} (- n)^{\underline{k}} = k = 0 \sum m S (m, k) (- 1)^{k} j = 0 \sum k s (k, j) (- n)^{j} = j = 0 \sum m n^{j} k = j \sum m S (m, k) s (k, j) (- 1)^{k - j}

反之亦然。

证明反演公式：

f (n) = i = 0 \sum n [i = n] f (i) = i = 0 \sum n f (i) j = i \sum n S (n, j) s (j, i) (- 1)^{j - i} = k = 0 \sum n S (n, k) i = 0 \sum k (- 1)^{k - i} s (k, i) f (i)

也就是说如果 $g$ 的定义式成立，那么 $f$ 成立。

用另一个反转公式，那么如果 $f$ 的定义式成立，那么 $g$ 成立。这样就证完了。

2018 雅礼集训方阵

给定 $n \times m$ 的矩阵，每个格子填上 $[1, c]$ 中的数字，求任意两行、两列均不同的方案数。
$n, m \leq 5000$ 。

不同：对应位置不同。

考虑只要求行不相同。

设 $g (m)$ 表示 $m$ 列的矩阵，行互不相同的方案数。有 $c^{m}$ 种可能的行。则

g (m) = (c^{m})^{\underline{n}}

$f (m)$ ： $m$ 列的答案。枚举 $g (m)$ 中列被分成多少类。

g (m) = i = 0 \sum m S (m, i) f (i) f (m) = i = 0 \sum m (- 1)^{m - i} s (m, i) g (i)

注： $f (0) = 0$ 。

一道例题

给定 n 个结点的树，从某个点出发开始随机游走：在点 u 时，有 $p_{u}$ 的概率留在原地，否则等概率向相邻结点移动，直到移动到 1 号点停下。求从每个结点出发直指停下，所花费的时间的 k 次方的期望。
$n \leq 1 0^{5}, k \leq 1 0^{5}, nk \leq 1 0^{6}$ 。

设 $u$ 到根结点的期望时间是 $t_{u}$ 。我们要求 $E (t_{u}^{k})$ 。

E (t_{u}^{k}) E ((i t _{u})) E ((i t _{u})) (1 - P_{u}) E ((i t _{u})) = E (i = 0 \sum k S (k, i) t_{u}^{\underline{i}}) = i = 0 \sum k S (k, i) i! E ((i t _{u})) = P_{u} E ((i t _{u} + 1)) + \frac{1 - P _{u}}{d _{u}} (u, v) \sum E ((i t _{v} + 1)) = P_{u} E ((i t _{u}) + (i - 1 t _{u})) + \frac{1 - P _{u}}{d _{u}} (u, v) \sum E ((i t _{v}) + (i - 1 t _{v} + 1)) = P_{u} E ((i - 1 t _{u})) + \frac{1 - P _{u}}{d _{u}} (u, v) \sum E ((i t _{v}) + (i - 1 t _{v} + 1))

考虑按照 $i$ 从小到大的顺序做。设 $E ((i t _{u})) = d p (u), E ((i - 1 t _{u})) = a_{u}$ ：

d p_{u} = P_{u} (d p_{u} + a_{u}) + \frac{1 - P _{u}}{d _{u}} (u, v) \sum (d p_{v} + a_{v}) d p_{u} = \frac{P _{u} a _{u}}{1 - P _{u}} + \frac{1}{d _{u}} (u, v) \sum (d p_{v} + a_{v})

可以按树上高消的套路做了。要记得 $O (k lo g_{2} k)$ 预处理斯特林数。

另一道例题

设连通块数为 T： $T^{k} = \sum_{i = 0}^{k} S (k, i) i! (i T)$ 。问题转化为求出 $\sum_{T} (i T)$ ，它表示选出了 $i$ 个连通块。

设 $d p_{t} (n)$ 表示 n 个点 t 个连通块的图的个数。

T \sum (i T) = j = 1 \sum n (j n) d p_{i} (j) 2^{(2 n - j)} A n s = i = 0 \sum k S (k, i) i! n! j = 1 \sum n d p_{i} (n - j) \frac{1}{( n - j )! j !} 2^{(2 j)}

问题转化为如何求 $\frac{d p _{i} ( j )}{j !}$ 。

d p_{t} (n) = i = 1 \sum n (i - 1 n - 1) d p_{1} (i) d p_{t - 1} (n - i) \frac{d p _{t} ( n )}{( n - 1 )!} = i = 1 \sum n \frac{d p _{1} ( i )}{( i - 1 )!} \frac{d p _{t - 1} ( n - i )}{( n - i )!}

那么

\hat{G}_{t} = n \geq 0 \sum d p_{t} (n) \frac{x ^{n}}{n !} \hat{F} = n \geq 1 \sum d p_{1} (n) \frac{x ^{n}}{( n - 1 )!}

容易得到

n \hat{G}_{t} = \hat{F} \hat{G}_{t - 1} + 1

$d p_{1} (n)$ 就是 $ln G (n)$ 。

清华集训 2017 生成树计数

在一个 s 个点的图中，存在 s-n 条边，使图中形成了 n 个连通块，第 i 个连通块中有 $a_{i}$ 个点。
现在我们需要再连接 n-1 条边，使得该图变成一棵树。对于一种连边方案，设原图中第 $i$ 个连通块连出了 $d_{i}$ 条边，那么这棵树 $T$ 的价值为：
$v a l (T) = (i = 1 \prod n d_{i}^{m}) (i = 1 \sum n d_{i}^{m})$
求出所有可能的生成树的价值之和，对 $998244353$ 取模。
$n \leq 3 \times 1 0^{4}, m \leq 30$ 。

转化为 n 个点的生成树 T：

= = (i = 1 \prod n d_{i}^{m}) (i = 1 \sum n d_{i}^{m}) (i = 1 \prod n a_{i}^{d_{i}}) T \sum i = 1 \sum n a_{i}^{d_{i}} d_{i}^{2 m} j \neq = i \prod (a_{j}^{d_{j}} d_{j}^{m}) \sum k_{i} = n - 2 \sum (k _{1} , k _{2} , \dots , k _{n} n - 2) i = 1 \sum n a_{i}^{k_{i} + 1} (k_{i} + 1)^{2 m} j \neq = i \prod (a_{j}^{k_{j} + 1} (k_{j} + 1)^{m})

交换

(n - 2)! i = 1 \sum n \sum k_{i} = n - 2 \sum \frac{1}{\prod k _{i} !} a_{i}^{k_{i} + 1} (k_{i} + 1)^{2 m} j \neq = i \prod a_{j}^{k_{j} + 1} (k_{j} + 1)^{m} (n - 2)! i = 1 \sum n \sum k_{i} = n - 2 \sum \frac{a _{i}^{k_{i} + 1} ( k _{i} + 1 ) ^{2 m}}{k _{i} !} j \neq = i \prod \frac{a _{j}^{k_{j} + 1} ( k _{j} + 1 ) ^{m}}{k _{j} !}

EGF

B_{i} (x) = k \geq 0 \sum a_{i}^{k + 1} (k + 1)^{2 m} \frac{x ^{k}}{k !} A_{i} (x) = k \geq 0 \sum a_{i}^{k + 1} (k + 1)^{m} \frac{x ^{k}}{k !}

带回

[x^{n - 2}] (n - 2)! i = 1 \sum n B_{i} (x) i \neq = j \prod A_{j} (x)

定义 $T (x)$ ：

T (x) = \int A_{i} (x) d x = k \geq 1 \sum a_{i}^{k} k^{m} \frac{x ^{k}}{k !} = k \geq 1 \sum a_{i}^{k} \frac{x ^{k}}{k !} j = 0 \sum m S (m, k) k^{\underline{j}} = j = 0 \sum m S (m, j) a_{i}^{j} x^{j} e^{a_{i} x}

那么复合函数求导得到（sum 里是个复合函数）

A_{i} (x) = \frac{d T ( x )}{d x} = j = 0 \sum m S (m, j) a_{i}^{j} j x^{j - 1} e^{a_{i} x} + j = 0 \sum m S (m, j) a_{i}^{j + 1} x^{j} e^{a_{i} x} = e^{a_{i} x} j = 0 \sum m S (m, j + 1) (j + 1) a_{i}^{j + 1} + S (m, j) a_{i}^{j + 1} = e^{a_{i} x} j = 0 \sum m S (m + 1, j + 1) a_{i}^{j + 1} x^{j}

复杂度 $O (nm lo g_{2}^{2} n)$ 。

Burnside 引理

ARC 62 F Painting Graphs with AtCoDeer

题意：给出无向图 G，对边染 K 种颜色之一。一个环上面的边旋转后得到的染色方案视为相同，求不同的染色方案数。

求出所有的点双（每个点双是独立的）：

单独的边：方案数为 K。
单环： $\frac{1}{n} \sum_{d = 0}^{n - 1} k^{g c d (n, d)}$ 。
复合环：可以交换两条边的颜色。只用统计不同颜色出现次数的方案数。插板 $(k - 1 n + k - 1)$ 。

乘起来即可。

「草稿」组合计数综合练习

文章目录

常见数列

容斥原理

ARC 102 E

集训队作业 2018 小 z 的礼物

ARC 96 E Everything on It

ARC 101 E Ribbons on Tree

ARC 93 F

斯特林反演

反演公式

反转公式

2018 雅礼集训方阵

一道例题

另一道例题

清华集训 2017 生成树计数

Burnside 引理

ARC 62 F Painting Graphs with AtCoDeer

修订记录

「草稿」组合计数综合练习

文章目录

常见数列

容斥原理

ARC 102 E

集训队作业 2018 小 z 的礼物

ARC 96 E Everything on It

ARC 101 E Ribbons on Tree

ARC 93 F

斯特林反演

反演公式

反转公式

2018 雅礼集训 方阵

一道例题

另一道例题

清华集训 2017 生成树计数

Burnside 引理

ARC 62 F Painting Graphs with AtCoDeer

修订记录

2018 雅礼集训方阵