The 2nd UCup Stage 7: Two Capitals. A.

令 $a_0 = a_{n+1} = m$，然后差分再反转，转化为计数长度为 $n+1$ 的整数序列，使得和为 $0$，且正数之和 $\le m$。 进一步转化为把括号对数 $\le m$ 的括号序列划分成 $n+1$ 个可以为空的段。其中同一段里不能同时出现两种括号。 立刻写出生成函数方程 $$ F(x, t) = x(1 + F(x, t))\left(\frac t{(1-t)^2} + \frac1{(1-t)^2} F(x, t)\right) $$ 而最后要求 $[x^m t^{n+1}] \frac{F(x, t)}{(1-x)(1-t)}$。 Lagrange 反演的**前途比较有限**，因此我们直接**大力解出方程**，然后考虑提取系数： $$ \begin{aligned} F(x, t) &= \frac{(1-t)^2-x(1+t^2)-\sqrt{((1-t)^2-x(1+t^2))^2-4x^2t^2}}{2x} \\ &= \frac{(1-t)^2\left(1-\sqrt{\left(1-x\frac{(1+t)^2}{(1-t)^2}\right)(1-x)}\right)-x(1+t^2)}{2x} \\ \frac{1+F(x, t)}{(1-x)(1-t)} &= \frac{(1-t)\left(1-\sqrt{\left(1-x\frac{(1+t)^2}{(1-t)^2}\right)(1-x)}\right)-x\frac{1+t^2}{1-t}}{2x(1-x)} + \frac1{(1-x)(1-t)} \\ [x^m t^{n+1}] \frac{1+F(x, t)}{(1-x)(1-t)} &= -1+1+[x^{m+1} t^{n+1}] \frac{(1-t)\left(1-\sqrt{\left(1-x\frac{(1+t)^2}{(1-t)^2}\right)(1-x)}\right)}{2(1-x)} \\ &= -[x^{m+1} t^{n+1}] \frac{(1-t)\sqrt{\left(1-x\frac{(1+t)^2}{(1-t)^2}\right)(1-x)}}{2(1-x)} \\ \end{aligned} $$ 注意到只有一个根式里同时有 $x, t$，且形式比较简单。 考虑枚举其中 $x$ 的次数。$\sqrt{1-x}, \frac1{\sqrt{1-x}}$ 的系数是熟知的，则我们需要对各 $k$ 求出 $$ [t^{n+1}] \frac{(1+t)^{2k}}{(1-t)^{2k-1}} $$ Lagrange 反演的**前途依然比较有限**，但幸运的是我们可以用**别的手法**处理。 $$ \begin{aligned} &\quad\; [t^{n+1}] \frac{(1+t)^{2k}}{(1-t)^{2k-1}} \\ &= [t^{n+1} u^{2k}] \frac{1-t}{1-u\frac{1+t}{1-t}} \\ &= [t^{n+1} u^{2k}] \frac{(1-t)^2}{(1-u)(1-t\frac{1+u}{1-u})} \\ &= [u^{2k}] \left(\frac{(1+u)^{n+1}}{(1-u)^{n+2}} - 2\frac{(1+u)^n}{(1-u)^{n+1}} + \frac{(1+u)^{n-1}}{(1-u)^n}\right) \end{aligned} $$ 也容易整式递推。 一个疑点是，通过 OEIS 等手段可以发现答案等于 $$ \frac1n \sum_{k=0}^n \binom nk \binom{2n-k}{n+1} \binom{m+1}{n-k} $$ 但不知有什么简洁的推导能够建立其与如上做法的联系，进一步地，在不知道规律的情况下如何从 GF 推出尽可能简洁的式子。