526互联

多项式计数相关

发布时间 2023-08-04 21:02:06作者: crimson000
title: 多项式计数相关
date: 2023-07-26 20:16:14
tags: 学习笔记
cover: https://gitcode.net/crimson000000/picture/-/raw/master/acdf1d40b4b6ae4131a956850489e873.jpg

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

来自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))\)。或者说指示了用有标号的元素构成的集合来生成集族有多少情况。

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

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

欧拉变换

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

  1. 我们认为盒子有序，那么我们前面就不用除去 \(k!\)，那么 \(G(x)=\sum \limits_{i=0} F^i(x) = \frac{1}{1-F(x)}\)。
  2. 无标号小球放入有标号盒子，那么只需要把前面的 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}\)，这样就做完了。

未完待续