处理 BGF diagonal 的经典方法

· · 个人记录

不妨以「『2021 年百度之星·程序设计大赛 - 初赛一』1002」为例。

我们先快进到生成函数

[s^n] (1+2cs)^n (1-s)^{-n-1}

官方题解在此考虑了逆用拉格朗日反演（事实上这是 idea 的来源），后来在 EI 哥哥的教育下出题人认识到了这是经典问题并且有经典方法。

写作 BGF

F(s,t) = \frac1{1-s}\frac1{1-t\frac{1+2cx}{1-s}}

不妨换元 t \to x/s，那么观察到原来的 s^i t^j 现在变成了 x^j s^{i-j}。
同时，现在的 x^i s^j 满足 i\ge 0, j \ge -i，因此其仍然是形式 Laurent 级数。
那么答案 \operatorname{diag}F(s,t) 无非就是 [s^0]F(s,x/s)。

令

G = F(s,x/s) = \frac{-s}{x+(2cx-1)s+s^2}

作分式分解，令

\left\{ \begin{aligned} \alpha &= \frac{1-2cx-\sqrt{1-4(c+1)x+4c^2x^2}}2 \\ \beta &= \frac{1-2cx+\sqrt{1-4(c+1)x+4c^2x^2}}2 \end{aligned} \right.

则

G = \frac{-s}{(s-\alpha)(s-\beta)} = \frac1{\beta-\alpha}\left(\frac{\alpha}{s-\alpha}-\frac{\beta}{s-\beta}\right)

接下来是一个重要的步骤：展开。
注意到 \frac{\alpha}{s-\alpha} 有两种展开方式：

\frac{\alpha/s}{1-\alpha/s} = \sum\limits_{n\ge 1} \alpha^n s^{-n}

和

\frac{-1}{1-s\alpha^{-1}} = -\sum\limits_{n\ge 0} \alpha^{-n} s^n

考虑之前提到的 x^i s^j 满足 j\ge -i，以及 \alpha,\beta 的最低次分别是 1,0，故应当展开为

[s^0]\frac1{\sqrt{1-4(c+1)x+4c^2x^2}} \left(\frac{\alpha/s}{1-s^{-1}\alpha}+\frac1{1-s\beta^{-1}}\right)

则答案为 \frac1{\sqrt{1-4(c+1)x+4c^2x^2}}。

同时这也证明了对于有理 BGF，其对角线必然是代数的。