The 3rd UCup Stage 1: St. Petersburg. L.

· · 个人记录

将 (a, b, c) 的坐标转化成 (a-b, a-c, a+b+c)，记做 (n, m, k)，方案数记做 a_{n, m, k}。

作其 GF Q(x, y; t) = \sum_{n, m, k} a_{n, m, k} x^n y^m t^k。

记 \overline{x} = 1/x，有方程

Q(x, y) = 1 + t (\overline x + \overline y + xy) Q(x, y) - t \overline x Q(0, y) - t \overline y Q(x, 0)

记 K(x, y) = 1 - t(\overline x + \overline y + xy)，方程变为

K(x, y) xy Q(x, y) = xy - t y Q(0, y) - t x Q(x, 0)

注意到由组合意义必定有 Q(x, y) = Q(y, x)，为了避免一些问题，将方程变为

K(x, y) xy Q(x, y) = xy - t y Q(y, 0) - t x Q(0, x)

注意到 K(x, y) 在 (x, y) \mapsto (\overline{xy}, y) 和 (x, y) \mapsto (x, \overline{xy}) 意义下都是不变的，从而我们可以总共得到三个方程

\begin{aligned} K(x, y) xy Q(x, y) &= xy - t y Q(y, 0) - t x Q(0, x) \\ K(x, y) \overline x Q(\overline{xy}, y) &= \overline x - t y Q(y, 0) - t \overline{xy} Q(0, \overline{xy}) \\ K(x, y) \overline y Q(\overline{xy}, x) &= \overline y - t x Q(x, 0) - t \overline{xy} Q(0, \overline{xy}) \end{aligned}

交错求和可以得到

K(x, y) \left(xyQ(x, y) - \overline x Q(\overline{xy}, y) + \overline y Q(\overline{xy}, x)\right) = xy - \overline x + \overline y - 2 txQ(x, 0)

需要注意的是，如果一开始没有对方程做转化，此处需要将六个方程交错求和，且右侧会得到 0。

注意到 xyQ(x, y) 的项满足 x, y 次数均为正，\overline x Q(\overline{xy}, y) 的项满足 x 次数均为负，\overline y Q(\overline{xy}, x) 的项满足 y 次数均为负，因此

Q(x, y) = \left[x^{\ge 0} y^{\ge 0}\right] \frac{1 - \overline{x^2y} + \overline{xy^2} - 2 t\overline yQ(x, 0)}{1 - t(\overline x + \overline y + xy)}

我们倾向于先算出 Q(x, 0)，即提取 [y^0]，这可以对 K(x, y) 以 y 为主元因式分解，然后将 \frac1{K(x, y)} 分式分解得到。

计算留作读者练习，接下来给出结果（来自 [1]）：记 W(t) 满足

W = t(2+W^3)

我们有

Q(x, 0) = \frac1{tx} \left(\frac1{2t} - \frac1x - \left(\frac1W - \frac1x\right) \sqrt{1-xW^2}\right)

通过 Lagrange 反演公式可以证明

[x^i t^{3m+2i}] Q(x, 0) = \frac{4^m(2i+1)}{(m+i+1)(2m+2i+1)} \binom{2i}i \binom{3m+2i}m

现在我们考虑提取

\begin{aligned} [x^n y^m t^k]Q(x, y) &= [x^n y^m] \left(1 - \overline{x^2y} + \overline{xy^2}\right)(\overline x + \overline y + xy)^k \\ &- 2[x^ny^{m+1}t^{k-1}] \frac{Q(x, 0)}{1 - t(\overline x + \overline y + xy)} \end{aligned}

第一项只有 O(1) 个位置有贡献，第二项可以枚举分母的展开，由于限定了 y 的次数所以需要枚举的只有平方级别。

时间复杂度 O((a+b+c)^2)。

[1] M. Bousquet-Melou and M. Mishna. Walks with small steps in the quarter plane. Contemporary Mathematics, 520:1–40, 2010.