生成函数的白给

略有标题党，只是为了让更多人点进来。 > 绚烂烟火 夜色绚丽 > 你的剪影 幻化成 琉璃 > 让它去散落 在这 白夜里 > ——《白夜梦》 执迷不悟一载有余——我们唯有打破自己的过去，让淋漓的鲜血渗透破碎的骨骼，让那最深的痛楚和绝望重逢，才有可能迎来重生。迷茫和绝望才是对的……因为没有痛苦就没有真实。 生成函数固然有用，但是它**仅仅**是组合工具中的一个分支，并没有一劳永逸的存在。在下才疏学浅，仅以自己一些微薄的尝试来试图说明一些问题： 在 [【集训队作业2018】count](http://uoj.ac/problem/424) 一题中，通过时限可以猜测出题人的做法应该是有多项式的 $\Theta(n\log n)$ 这种，我们首先看看用生成函数来推会得到什么： 显然，我们只需求出有多少种可生成的笛卡尔树，这等价于左偏深度 $\le m$，那么我们可以得到 $F_0(x)=1, F_m(x) = 1 + xF_{m-1}(x)F_m(x)$，即 $F_m(x) = \frac1{1-xF_{m-1}(x)}$，答案在 $n\ge m$ 时就是 $[x^n]F_m(x)$。 迭代列一般而言是困难的，庆幸的是本题的迭代列符合莫比乌斯变换形式。设 $F_m(x) = \frac{A(x)}{B(x)}$，那么可得 $$ \left( \begin{matrix} A \\ B \\ \end{matrix} \right) = \left( \begin{matrix} & 1 \\ -x & 1 \\ \end{matrix} \right)^m \left( \begin{matrix} 1 \\ 1 \\ \end{matrix} \right) $$ 由矩阵的特征根是 $\frac{1 \pm \sqrt{1-4x}}2$，我们可以解得 $A,B$ 的通项是 $$ \begin{aligned} A(x)&=-\frac{2^{-m-1} \left(-\sqrt{1-4 x}-1\right) \left(1-\sqrt{1-4 x}\right)^m}{\sqrt{1-4 x}}-\frac{2^{-m-2} \left(-\sqrt{1-4 x}-1\right) \left(\sqrt{1-4 x}-1\right) \left(1-\sqrt{1-4 x}\right)^m}{\sqrt{1-4 x} x}\\&\quad+\frac{2^{-m-1} \left(\sqrt{1-4 x}-1\right) \left(\sqrt{1-4 x}+1\right)^m}{\sqrt{1-4 x}}-\frac{2^{-m-2} \left(\sqrt{1-4 x}-1\right) \left(\sqrt{1-4 x}+1\right)^{m+1}}{\sqrt{1-4 x} x}\\ B(x)&=\frac{2^{-m} x \left(1-\sqrt{1-4 x}\right)^m}{\sqrt{1-4 x}}+\frac{2^{-m-1} \left(\sqrt{1-4 x}-1\right) \left(1-\sqrt{1-4 x}\right)^m}{\sqrt{1-4 x}}\\&\quad-\frac{2^{-m} x \left(\sqrt{1-4 x}+1\right)^m}{\sqrt{1-4 x}}+\frac{2^{-m-1} \left(\sqrt{1-4 x}+1\right)^{m+1}}{\sqrt{1-4 x}} \end{aligned} $$ 所以有 $$ F_m(x) = \frac{\sqrt{1-4 x} \left(1-\sqrt{1-4 x}\right)^m-\left(1-\sqrt{1-4 x}\right)^m+\left(\sqrt{1-4 x}+1\right)^m+\sqrt{1-4 x} \left(\sqrt{1-4 x}+1\right)^m}{(2 x-1) \left(1-\sqrt{1-4 x}\right)^m+\sqrt{1-4 x} \left(1-\sqrt{1-4 x}\right)^m+(1-2 x) \left(\sqrt{1-4 x}+1\right)^m+\sqrt{1-4 x} \left(\sqrt{1-4 x}+1\right)^m} $$ 如果你觉得不好，倒是可以稍微让形式看起来便于“计算”一点。 $$ F_m(x)=1+\dfrac{2x}{1-2x+\sqrt{1-4x}\dfrac{1+\left(\dfrac{1-\sqrt{1-4x}}{1+\sqrt{1+4x}}\right)^m}{1-\left(\dfrac{1-\sqrt{1-4x}}{1+\sqrt{1+4x}}\right)^m}} $$ 是的，我们得到了一个做法。但是无疑，**计算繁琐**。更大的问题在于这个题目明明换一个做法就可以得到非常清爽的答案形式，事实上我们从之前推导的哪一步就开始绕远路了呢？ > 这等价于左偏深度 $\le m$…… 我们注意到方案数等价于一个共计 $n$ 对推栈退栈的序列，其中任何时刻的栈大小不超过 $m$。也就是说，这是一个被两条线 bound 住的二维游走问题。这个问题可以通过折线法容斥表示。 > 事实上，折线法原本就在这个问题上比生成函数优越呢。 问题转为，一个格路计数不能碰触 $-1, m+1$ 这两条线。这是一个经典容斥，通过沿折线反射即可将答案表示为 $\Theta(n/m)$ 个组合数。 在路径问题上的无力则更能体现在 [EC Final 2019 B. Black and White](https://codeforces.com/gym/102471/problem/B) 一题中。 若尝试使用生成函数进行推导，考虑将任意两个相邻的相同方向行进消掉，显然未影响扫过方块的代数和，而经此约化后的可能路径只有常数中情况。接下来我们考虑如何表示，设向两个方向走动的占位元分别是 $x, y$，那么一个 $x$ 在约化前之前附带的可能行进记为 $f(x, y)$，我们发现 $$ \begin{aligned} f(x, y) & = \frac1{1- yf(y,x)y}\\ &= \frac1{1-y^2f(y,x)}\\ &= \frac1{1-\frac{y^2}{1-x^2f}}\\ &= \frac{1+x^2-y^2 - \sqrt{(1+x^2-y^2)^2 - 4x^2}}{2x^2} \end{aligned} $$ 这意味着我们主要问题在于求算 $f(x,y)^{\lfloor k/2\rfloor} f(y,x)^{\lceil k / 2\rceil}$ 的一个项系数，这个形式确实存在一定代数上的困难性，看起来很难直接推出提取某项系数的公式。事实上笔者当时尝试过各方向的变形，由于均未走通，不予呈现。直到重新思考，发现…… 考虑如此构造：对于一个变量 $v$，在第奇数步向右走就 $+1$ 否则 $-1$，偶数步倒过来，那么 $v \in [4k - 2, 4k + 1]$，那么对于给定 $(n, m, v)$ 的方案数用组合数就可以表示。这样一来，实际上我们可以推出方案数仅仅是由 $2$ 个组合数表示的。很难相信通过代数推导能确立该组合数与生成函数的对应关系。 这两个例子无疑是一个警钟：就算能列出生成函数的式子，就一定容易推导出足够优秀的结果吗？我们还有更多的例子体现出生成函数方法的局限，其蕴含的初等运算恐怕并不足够具有洞察力以支持得到，通过特殊的组合对象得出的结论的水平。更休说若干对象：杨表、prüfer 编码、Dyck 路以及一些乱七八糟的路径计数…… > 待从头、收拾旧山河，朝天阙。 > > ——岳飞《满江红》