放假太闲了，也没啥游戏可玩，于是学学科技
前言
本博客直接嗯看的话一开始跨度会比较大，因此不建议没有了解过以下内容的人观看。
- 多项式以及多项式的一些初等函数
- 生成函数的简单了解，包括 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}$，这样就做完了。