Zscoder‘s 生成函数教程（三）

本文翻译自 zscoder 的 CF Blog 文章 [Tutorial] Generating Functions in Competitive Programming (Part 2) 。

本文是原文的第二部分，生成函数在 CP 中实战。

如有侵权，联系作者将尽快删除；如有翻译不足之处，敬请指出。

注意：除非有特殊情况，我们都是在模 $998244353$ 的意义下计算。 $[n]$ 指的是集合 $\{1,2,3,\dots ,n\}$ 。

显然的计数问题

问题。AGC 005 Problem F。

首先，我们需要做一个基础计数。对于一个顶点集 $S$ ，令 $t(S)$ 为包含 $S$ 的最小的子树。

固定 $k$ 的情况下如何计算 $f(S)$ 呢？如果我们单独看一个顶点 $v$ ，计算有多少个大小为 $k$ 的 $S$ 满足 $t(S)$ 包含 $v$ 是比较困难的。然而，我们单独的看一个边 $e$ ，计算有多少个大小为 $k$ 的 $S$ 满足 $t(S)$ 包含 $e$ 是相对简单的。我们只需要删去 $e$ 然后在两个连通分量中选择 $k$ 个节点，这些节点的 $t(S)$ 是一定包含 $e$ 的。换句话说，如果我们删除 $e$ 那么整棵树就变成了两个大小分别为 $a$ 和 $n-a$ 的连通分量，我们计算 ${\sum }_{e\in E}\left(\genfrac{}{}{0ex}{}{n}{k}\right)-\left(\genfrac{}{}{0ex}{}{a}{k}\right)-\left(\genfrac{}{}{0ex}{}{n-a}{k}\right)$ ，这些是 $t(S),|S|=k$ 中所有边的数量，又因为在树中点的数量等于边的数量加一，因此 ${ans}_k=\left(\genfrac{}{}{0ex}{}{n}{k}\right)+{\sum }_{e\in E}\left(\genfrac{}{}{0ex}{}{n}{k}\right)-\left(\genfrac{}{}{0ex}{}{a}{k}\right)-\left(\genfrac{}{}{0ex}{}{n-a}{k}\right)$ 。

通过dfs，我们能计算出所有的 $a$ ，记为 $a_1,a_2,\dots ,a_{n-1}$ 。如果我们能快速计算出对于所有 $1\le k\le n$ 和式 ${\sum }_{i=1}^{n-1}\left(\genfrac{}{}{0ex}{}{a_i}{k}\right)$ 的值，那我们的问题就解决了。

我们使用一个小技巧，令 $c_i$ 为 $i$ 出现在 $a_1,a_2,\dots ,a_{n-1}$ 中的次数，那么我们所求为 ${\sum }_{i=0}^n{c}_i\left(\genfrac{}{}{0ex}{}{i}{k}\right)$ 。

接下来使用一个打开组合数的一个套路：

$$\sum _{i=0}^n{c}_i\left(\genfrac{}{}{0ex}{}{i}{k}\right)=\sum _{i=0}^n{c}_i\frac{i!}{k!(i-k)!}=\frac{1}{k!}\sum _{i=0}^{n}i!c_i\frac{1}{(i-k)!}$$

显然，我们只需要知道如何对于所有的 $k$ 快速计算 ${\sum }_{i=0}^{n}i!c_i\frac{1}{(i-k)!}$ 。如果你学过生成函数，这非常像两个生成函数的卷积。我们引入 $F(x)={\sum }_{i\ge 0}f(i)x^i$ 和 $G(x)={\sum }_{i\ge 0}g(i)x^i$ 。

那么 $C(x)={\sum }_{k\ge 0}{x}^k{\sum }_{i=0}^{n}i!c_i\frac{1}{(i-k)!}={\sum }_{k\ge 0}{x}^k{\sum }_{i=0}^{n}f(i)g(k-i)=F(x)G(x)$ 。

显然，我们令 $f(i)=i!c_i$ 而 $g(i)=\frac{1}{(-i)!}$ ，然而当 $i>0$计算 $(-i)!$ 是没有意义的。问题不大，我们只需要平移我们的生成函数，让 $x^{-i}$ 部分移动至 $x^{n-i}$ 。此时，当我们想获取原生成函数的 $x^k$ 次项系数的时候，我们需要获取新生成函数的 $x^{k+n}$ 次项。

AC 代码

遇到卷积问题通常使用生成函数和多项式求解，然而生成函数的强大远不及此。

问题。CF438 E

这在六年前是一道 3100 分的题目，但是现在你已经在2020年知道了多项式算法（这个年代多项式算法已经非常普及），那就非常简单了。

首先，显然的构造 $f_s$ 是我们对于 $s$ 的答案，令 $F(x)$ 为 $f_s$ 的 OGF 。

显然，$f_0=1$ 。对于 $s>0$ 我们模仿 Catalan 数找到一个递归式：

$$f_s=\sum _{c\in C}\sum _{i\ge 0}{f}_i{f}_{s-c-i}$$

用生成函数的语言表达，就是：

$$\sum _{s\ge 1}{f}_s{x}^s=\sum _{s\ge 1}\sum _{c\in C}{x}^c\sum _{i\ge 0}{f}_i{x}^i{f}_{s-c-i}{x}^{s-c-i}$$

令 $F(x)={\sum }_{s\ge 0}{f}_s{x}^s$ 和 $C(x)={\sum }_{c\in C}{x}^c$ 那么上面的式子不就是：

$$F(x)-1=F(x{)}^{2}C(x)$$

解这个二次方程得到 $F(x)=\frac{1\pm \sqrt{1-4C(x)}}{2C(x)}$ ，当 $x\to 0$ 的时候， $F(x)\to 1$ 使用洛必达法则确定符号为负号，因此 $F(x)=\frac{1-\sqrt{1-4C(x)}}{2C(x)}$ 。

到这里我们基本就做完了，但是还有个实现上的细节。我们知道 $C(x)$ 的常数项为 $0$ 这代表 $C(x)$ 没有逆元。我们对上面的式子进行分子有理化：

$$F(x)=\frac{1-\sqrt{1-4C(x)}}{2C(x)}=\frac{(1-\sqrt{1-4C(x)})(1+\sqrt{1-4C(x)})}{2C(x)(1+\sqrt{1-4C(x)})}=\frac{4C(x)}{2C(x)(1+\sqrt{1-4C(x)})}=\frac{2}{1+\sqrt{1-4C(x)}}$$

我们要计算前 $m$ 项，因此使用多项式算法的时间复杂度为 $O(m\log m)$ 。

AC 代码

实话说，也不能说这个题简单因为主要的难点在于计算多项式的平方根和多项式的倒数，这在6年前很少有人知道，但是在现在你可以在网上找到大量多项式的板子，我们只需要思考问题本身。

问题。Simple Counting

这道题有一个 $O(\frac{n^2}{k})$ 的 DP 算法（试一试），但是无法通过这道题目。我们需要使用生成函数。令 $f(n)$ 是我们的答案（ $k$ 是固定的）。

关键的思想就在于“恰好”条件是困难的，而“至少”条件是简单的。令 $f(S)$ 指的是恰好只在点集 $S$ 处下降的排列数量。而 $g(S)$ 是在点集 $S$ 的任意子集处下降的排列数量。显然 $g(S)={\sum }_{T\in S}f(T)$ 。使用容斥原理，我们能得到 $f(S)=\sum _{T\subseteq S}(-1{)}^{|S|-|T|}g(T)$ 。

$g(S)$ 实际上更好计数。假设 $S=\{s_1,s_2,\dots ,s_m\}$ 在这里 $s_i<s_{i+1}$ 。一个更好的理解就是将整个排列分成 $m$ 块上升的块。这等于将 $n$ 个元素分成 $m$ 类，也就是 $\frac{1}{s_1!(s_2-s_1)!(s_3-s_2)!...(n-s_m)!}$ 。因此 $g(S)=\frac{n!}{s_1!(s_2-s_1)!(s_3-s_2)!...(n-s_m)!}$ 。

为了简单，我们令 $D=k,2k,3k,\dots \cap [n-1]$ 。我们需要计算 $f(D)$ 。

任何的 $D$ 的子集 $T=\{s_1,s_2,\dots ,s_{m-1}\}$ （以升序排列）能够描述为 $b_1,b_2,\dots ,b_m$ 其中 $b_i=s_i-s_{i-1}$ 。特别的 $s_0=0,s_m=n$ 指的是每一块的大小。将 $g(T)$ 化简为 $G(T)=\frac{n!}{b_1!b_2!\dots b_m!}$ 。

因此：

$$f(D)=\sum _{T\subseteq D}(-1{)}^{|D|-|T|}g(T)=\sum _{\sum b_i=n,b_i\text{ good}}(-1{)}^{|D|-(m-1)}\frac{n!}{b_1!b_2!...b_m!}$$

为了表示简单，我们将长度 $n$ 表示为 $kq+r$ 的这种形式，注意因为当 $n$ 是 $k$ 的倍数的时候位置 $n$ 不应该考虑，因此 $1\le r\le k$ 。我们使用 EGF。

$$F(x)=\sum _{q\ge 0}\frac{f(kq+r)}{(kq+r)!}{x}^{kq+r}$$

$$=\sum _{q\ge 0}\sum _{m\ge 1}\sum _{\sum b_i=kq+r,b_i\text{ good}}(-1{)}^{q-m+1}\frac{(kq+r)!}{b_1!b_2!...b_m!}\cdot \frac{x^{kq+r}}{(kq+r)!}$$

$$=\sum _{m\ge 1}\sum _{q\ge 0}\sum _{\sum b_i=kq+r,b_i\text{ good}}(-1{)}^{q-m+1}\frac{x^{b_1}\cdot x^{b_2}\cdot ...\cdot x^{b_m}}{b_1!b_2!...b_m!}$$

$$=\sum _{m\ge 1}{\left(\sum _{i\ge 1}\frac{(-1{)}^{i-1}\cdot x^{ki}}{(ki)!}\right)}^{m-1}\cdot \left(\sum _{i\ge 0}\frac{(-1{)}^i\cdot x^{ki+r}}{(ki+r)!}\right)$$

花一点时间理解一些最后一个卷积。我们卷 $m-1$ 次整区间，最后一次卷积包含 $r$ 。

继续化简我们得到：

$$=\left(\sum _{i\ge 0}\frac{(-1{)}^i\cdot x^{ki+r}}{(ki+r)!}\right)\cdot \sum _{m\ge 1}{\left(\sum _{i\ge 1}\frac{(-1{)}^{i-1}\cdot x^{ki}}{(ki)!}\right)}^{m-1}$$

$$=\left(\sum _{i\ge 0}\frac{(-1{)}^i\cdot x^{ki+r}}{(ki+r)!}\right)\cdot \frac{1}{1-\left(\sum _{i\ge 1}\frac{(-1{)}^{i-1}\cdot x^{ki}}{(ki)!}\right)}$$

$$=\frac{\sum _{i\ge 0}\frac{(-1{)}^i\cdot x^{ki+r}}{(ki+r)!}}{\sum _{i\ge 0}\frac{(-1{)}^i\cdot x^{ki}}{(ki)!}}$$

我们在 O(n \log n) 的情况下能计算出第 $n$ 项，这道题就做完了。通过 EGF ，你能够消去分子中的阶乘分配分母的阶乘构造卷积。

AC 代码