题解 P5748 【集合划分计数】

· · 题解

我的博客

题意就是求 10^5 以内所有贝尔数，bell(n) 即将 n 个有标号的球划分为若干集合的方案数。

我们设一个非空集合的指数生成函数为 F(x)，设答案的指数生成函数为 G(x)；

枚举一共用多少个集合，将这些集合组合起来，集合之间是不可区分的。

G(x)=\sum_{i=0}^\infty \frac{F^i(x)}{i!}

也就是一个 多项式exp 的形式

G(x)=e^{F(x)}

而显然有非空集合的指数生成函数

F(x)=e^x-1

那么我们就可以求出贝尔数的指数生成函数 G(x) 了，注意答案乘上 n!。