学习笔记

~~放假太闲了，也没啥游戏可玩，于是学学科技~~

来自hosen学长的亲切关怀

前言

本博客直接嗯看的话一开始跨度会比较大，因此不建议没有了解过以下内容的人观看。

多项式以及多项式的一些初等函数
生成函数的简单了解，包括 OGF 和 EGF（仅限了解即可）
组合数学

指数生成函数 exp 的组合意义

我们考虑下面这个问题：

有 $n$ 个不同的小球，我们设 $k$ 个小球放入一个盒子中的方案数为 $f_k$ （显然在球和盒子的问题中 $f_i=1$ ，但是有时我们需要研究 $f_i$ 不等于 $1$ 的情况）。求下面两个问题的答案：

$n$ 个不同的小球放入 $k$ 个互不区分的盒子中的方案数
$n$ 个不同的小球放入任意个互不区分的盒子中的方案数

我们设第一个问题的答案为 $G_k[n]$ ，枚举 $k$ 个盒子中都放多少个小球，我们有下面的式子：

G_k[n]=\frac{n!}{k!}\sum \limits_{a_1+a_2+\cdots a_k=n}\frac{f_{a_1}f_{a_2}\cdots f_{a_k}}{a_1!a_2!\cdots a_k!}

我们设 $f_i$ 的 EGF 为 $F(x)$ ， $G_k[i]$ 的 EGF 为 $G_k(x)$ ，上面的式子就可以写成：

G_k(x)=\frac{1}{k!}F^k(x)

多项式快速幂即可解决。

而对于第二个问题，我们只需要枚举有多少个盒子即可。我们就可以写出下面的式子：

\begin{aligned} G(x) & = \sum \limits_{i = 0}^{+\infty} G_i(x) \\ &= \sum \limits_{i = 0}^{+\infty} \frac{F^i(x)}{i!} \\ \end{aligned}

根据 $e^x=\sum \limits_{i=0}^{+\infty} \frac{x^i}{i!}$ （麦克劳林展开），我们可以得到下面的式子：

G(x)= \mathrm{exp}(F(x))

出奇的简洁，对吧。这也就是指数生成函数 $\mathrm{exp}$ 的组合意义，既将 $n$ 个互异元素划分为任意非空的无序集合中，其中大小为 $i$ 的集合方案数为 $f_i$ ，最后总方案数为 $g_n$ ，则两者 EGF 满足 $G(x)=\mathrm{exp} (F(x))$ 。或者说指示了用有标号的元素构成的集合来生成集族有多少情况。

如果上面这些话比较抽象，可以参照下面的两个个例子来理解：

有标号的小球放到一个盒子是集合，它能够通过 $\mathrm{exp}$ 来转化为放到一堆盒子中的情况。
有标号的点形成连通块是集合，它能够转化为一堆连通块，也就是普通图。

欧拉变换

再回到小球和盒子上来，我们还可以解决下面这几个问题：

我们认为盒子有序，那么我们前面就不用除去 $k!$ ，那么 $G(x)=\sum \limits_{i=0} F^i(x) = \frac{1}{1-F(x)}$ 。
无标号小球放入有标号盒子，那么只需要把前面的 EGF 换为 OGF 即可。

我们需要解决的问题主要在下一种：无标号小球放入无标号盒子。我们设生成函数 $F(x)=\sum \limits_{i=0} f_i x^i$ 。那么我们对大小为 $i$ 的盒子构造完全背包的生成函数，既 $\frac{1}{1-x^i}$ ，那么这些盒子的方案数即为 $\frac{1}{(1-x^i)^{f_i}}$ ，我们就可以得到欧拉变换的定义式：

\mathcal{E}(F(x))=\prod_{i=1}^{+\infty}\frac{1}{(1-x^i)^{f_i}}

我们考虑把它化简一下，化简的具体过程可以参考我的十二重计数法博客，下面过程可能会略微省略。

\begin{aligned} \mathcal{E}(F(x)) & = \prod_{i = 1}^{+\infty}\frac{1}{(1-x^i)^{f_i}}\\ &= \mathrm{exp}(\sum_{i=1} f_i\ln\frac{1}{1-x^i})\\ &=\mathrm{exp}(\sum \limits_{i=1} f_i\sum \limits_{j=1}\frac{x^{ij}}{j})\\ &=\mathrm{exp}(\sum \limits_{j=1} \frac{1}{j}\sum \limits_{i=1}f_i x^{ij})\\ &=\mathrm{exp}(\sum \limits_{i=1} \frac{F(x^i)}{i})\\ \end{aligned}

这样就得到了欧拉变换的最终式子，欧拉变换的组合意义和 $\mathrm{exp}$ 类似，但是它主要是用来解决无标号问题的，我们在下面的习题中会看到类似的题目。

一些题目

限于作者能力和精力有限，只能找一些板题来当例题了。

集合划分计数

一个有 $n$ 个元素的集合，将其分为任意个非空无序子集，求方案数。

数据范围： $T = 1000$ ， $1\le n \le 10^5$ 。

和上面第一个提到的例子相同，只不过为 $f_i=[i>0]$ 的特殊情况。按照上面的式子写即可。

城市规划

求 $n$ 个点有标号无向连通图的数量。

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

在计数杂题中，我们已经介绍了基于 DP 的分治 FFT 做法，这里我们再介绍基于 $\mathrm{exp}$ 的组合意义的做法。

我们考虑一张简单无向图是如何组成的：是由一堆有标号点构成的连通块组成的。我们把上面的例子套到这里：小球即为有标号点，盒子即为连通块。只不过这里小球放入一个盒子中的方案数不为 $1$ 了，我们设方案数为 $f_i$ 。而放到任意多个盒子中的方案数我们设为 $g_i$ ，易得 $g_n=2^{\dbinom{n}{2}}$ 。根据 $\mathrm{exp}$ 的组合意义，很容易得到下面的式子：

\begin{aligned} G(x)&=\mathrm{exp}(F(x))\\ F(x)&=\ln (G(x)) \end{aligned}

多项式 $\ln$ 即可。

有标号 DAG 计数

对 $n$ 个点有标号的有向无环图进行计数，要求：弱连通图（所有的有向边替换为无向边后的图为连通图）。

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

设 $f_i$ 为大小为 $i$ 的普通 DAG（可能不连通）的数量。

我们考虑模拟拓扑排序的过程，我们删去图中的 $j$ 个零入度点，剩下的图仍然是一张 DAG。我们就能得到下面的式子：

f_i=\sum \limits _{j=1}^{i-1}\dbinom{i}{j} (-1)^{j+1}f_{i-j}2^{j(i-j)}

注意这里我们乘了一个 $(-1)^{j+1}$ ，因为我们注意到我们没有保证恰好 $j$ 个零入度点，所以要容斥一下。而 $2^{j(i-j)}$ 是因为这 $j$ 个点可以对剩下的 $(i-j)$ 个点选择连或不连边。因此公式为这个。我们考虑化简这个式子：

首先这个 $\dbinom{i}{j}$ 很好处理，取两边的 EGF 即可，而对于 $2^{j(i-j)}$ ，我们可以把它用下面这个式子化简： $j(i-j)=\dbinom{i}{2}-\dbinom{j}{2}-\dbinom{i-j}{2}$ 。这个式子易证，我们就可以把 $2^{j(i-j)}$ 化为 $\frac{2^{\dbinom{i}{2}}}{2^{\dbinom{j}{2}}\times 2^{\dbinom{i-j}{2}}}$ 。这样我们构造下面这两个生成函数：

F(x)= \sum \limits_{i=0}\frac{f_i}{2^{\dbinom{i}{2}}\times i!}x^i

G(x)= \sum \limits_{i=0}\frac{(-1)^{i+1}}{2^{\dbinom{i}{2}}\times i!}x^i

我们就能得到这个式子： $F(x)=F(x)G(x)+1$ ，这里加一是因为有 $F[0]=1$ 。解方程即可得到 $F(x)=\frac{1}{1-G(x)}$ 。

我们得到了普通 DAG 的答案，我们考虑弱连通 DAG。一个普通 DAG 一定是由一堆弱连通的 DAG 构成，因此它也符合我们 $\mathrm{exp}$ 的组合意义。因此我们只需要取一下 $\ln$ 即可。

无标号无根树计数

求 $n$ 个点的无标号无根树数量。

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

本题是无标号问题，因此我们需要用上面提到的欧拉变换来解决。

我们先考虑有根树。我们把根去掉后，会形成一堆小的无标号有根树。如果我们把一棵树看作一个集合，那么这一堆树就是生成集族。通过比较系数我们就可以用欧拉变换列出下面的式子：

F(x)=x\mathcal{E}(F(x))

这么简洁的式子不出意料的难解决。我们考虑对两边求导。

\begin{aligned} F(x)&=x\mathcal{E}(F(x))\\ F(x)&=x\times \exp(\sum \limits_{i=1}\frac{F(x^i)}{i})\\ F'(x)&=x'\times \exp(\sum \limits_{i=1}\frac{F(x^i)}{i})+x\times \left ( \exp(\sum \limits_{i=1}\frac{F(x^i)}{i}) \right )'\\ &=\frac{F(x)}{x}+x\times \exp(\sum \limits_{i=1}\frac{F(x^i)}{i})\times \left (\sum \limits_{i=1}\frac{F(x^i)}{i}\right )'\\ &=\frac{F(x)}{x}+F(x)\times \left (\sum \limits_{i=1}\frac{F'(x^i)\times i\times x^{i-1}}{i}\right )\\ &=\frac{F(x)}{x}+F(x)\times \left (\sum \limits_{i=1}\frac{F'(x^i)\times i\times x^{i-1}}{i}\right )\\ &=\frac{F(x)}{x}+F(x)\left (\sum \limits_{i=1}F'(x^i)\times x^{i-1}\right )\\ xF'(x)&=F(x)+F(x)\sum \limits_{i=1}F'(x^i)\times x^{i} \end{aligned}

我们发现右边这个 $\sum \limits_{i=1}F'(x^i)\times x^{i}$ 及其恶心，我们设 $G(x)=\sum \limits_{i=1}F'(x^i)\times x^{i}$ ，则

\begin{aligned} G(x) & = \sum \limits_{i = 1}F'(x^i)\times x^{i}\\ &=\sum \limits_{i = 1} x^{i}\sum \limits_{j=1}jf_jx^{i(j-1)}\\ &=\sum\limits_{i=1}\sum \limits_{j=1}jf_jx^{ij}\\ \end{aligned}

因此所有对 $G(x)$ 第 $n$ 项系数有 $j\times f_j$ 的贡献的 $j$ 必须满足 $j|n$ 。因此 $[x^n]G(x)=\sum \limits _{i|n}i\times f_i$ 。

我们再把 $G(x)$ 带回去，能够得到 $xF'(x)-F(x) = F(x)G(x)$ 。而我们发现 $xF'(x)=\sum \limits _{i=1}i\times f_i\times x^i$ ，因此我们能得到下面的式子：

\begin{aligned} \left [ x^n \right ] F(x)&=\frac{\left [ x^n\right ]F(x)G(x)}{n-1}\\ f_n&=\frac{\sum \limits_{i=0}^{n-1}f_ig_{n-i}}{n-1} \end{aligned}

分治 FFT 即可。注意这里的分治 FFT 和 luogu 上的板子题不太一样， $g_i$ 是依赖于已经计算过的 $f_i$ 的，因此我们需要采取下面的方式转移：

当 $l = 0$ 时， $f_{l\sim mid}\times g_{0\sim r-l}\to f_{mid\sim r}$ 。

当 $l\not= 0$ 时，转移为：

\left.\begin{matrix} f_{l\sim mid}\times g_{0\sim r-l}\\ g_{l\sim mid}\times f_{0\sim r-l} \end{matrix}\right\}\to f_{mid\sim r}

这样我们就求出了有根树的数量，我们再考虑无根树的数量，我们只需要给它定个根：重心。减去不合法的（子树大小大于 $\frac{n}{2}$ 的），这样答案即为：

f_n-\sum \limits _{i=\left \lfloor \frac{n}{2} \right \rfloor+1 }^{n-1}f_if_{n-i}

但是我们考虑偶数个点可能会有两个重心，因此我们需要再减去当这两颗大小相同的树同构的情况，也就是 $\dbinom{f_{\frac{n}{2}}}{2}$ ，这样就做完了。

多项式计数相关

前言

指数生成函数 exp 的组合意义

欧拉变换

一些题目

未完待续