Tony102's Blog - 贝尔数
type: channel
link: https://tony102.com/index.php/tag/%E8%B4%9D%E5%B0%94%E6%95%B0/
items: Luogu5748 集合划分计数

Luogu5748 集合划分计数
type: item
date: 2021-03-25T19:56:00+08:00
description: LinkSol贝尔数就是一行第二类斯特林数的和，关于贝尔数和第二类斯特林数之间一些转换关系，此处不再赘述首先给出贝尔数的递推公式$$B_n = \sum_{i = 1}^{n} B_{n - i} \binom{n - 1}{i - 1}$$组合意义显然意见，把集合划分成 $n$ 个非空子集的方案数就可以先枚举某一特定元素所在集合的大小，比如说考虑 $1$ 这个元素所在的集合是 $\binom{n - 1}{i - 1}$ 种，那么剩下的元素划分的方案数就是 $B_{n - i}$$i - 1$ 不好搞，把枚举 $i$ 换成枚举 $i - 1$ ，就变成了$$B_n = \sum_{i = 0}^{n - 1} B_{n - i - 1} \binom{n - 1}{i}$$把组合数拆开，并且把两边同时乘上 $x^{n - 1}$ ， 得到：$$B_n x^{n - 1} = \sum_{i = 0}^{n - 1} \frac{(n-1)! x^{n-1}}{i! (n - i - 1)!} B_{n - i - 1}$$这玩意儿你一看十分不好做，但是如果观察看见 $x^{i} \times x^{n - i - 1} = x^{n - 1}$ ，事情就简单了不少$$B_n x^{n - 1} = \sum_{i = 0} ^{n - 1} \frac{x^{i}}{i!} \cdot \frac{B_{n - i - 1}}{(n - i - 1)!} x^{n - i - 1} \cdot (n - 1)!$$把 $(n - 1)!$ 项除过去，现在已经变成了：$$\frac{B_n}{(n - 1)!} x^{n - 1} = \sum_{i = 0}^{n - 1} \frac{x^{i}}{i!} \cdot \frac{B_{n - i - 1}}{(n - i - 1)!} x^{n - i - 1}$$对其求导，得：$$\frac{\mathrm{d}}{\mathrm{d}x} (\frac{B_n}{n!} x ^{n}) = \sum_{i + j = n - 1} \frac{x^i}{i!} x^i \cdot \frac{B_j}{j!} x^j $$设贝尔数的 EGF 为$F(x)$ ， 上面的式子已经是一个 EGF 的形式了，所以重写变成$$\frac{\mathrm{d} }{\mathrm{d} x} F'(x) = F(x) \cdot e^x$$设 $u = F(x)$ ， 两边同时乘以算子 $\mathrm{d} x$$$\mathrm{d} u = u \cdot e^x \cdot \mathrm{d} u$$把右边的 $u$ 除过去$$\frac{\mathrm{d} u}{u} = e^x \cdot \mathrm{d} u$$积分得$$\int \frac{\mathrm{d} u}{u} = \int e^x \mathrm{d} x$$$$\ln u = e^x + C$$把 $x = 1$ 带入 EGF 的时候可以算出一个 $C = -1$ ，所以$$F(x) = e^{e^x - 1}$$因为 $e^x - 1 = \sum_{n \geq 1} \frac{1}{n!} x^n$所以把阶乘逆元作为初始多项式再做 exp 就好了Code#include <bits/stdc++.h> #define int long long using namespace std; const int SIZE = 2e6 + 5, siz = 1e5; const int G = 3, Gi = 332748118, mod = 998244353; int n; int f[SIZE], g[SIZE], c[SIZE], lne[SIZE], iv[SIZE], cal[SIZE], pos[SIZE], W[SIZE], WN[SIZE], fac[SIZE], inv[SIZE]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch…