Problem G. Perfect Strings

未分类

---

还是括号匹配，再转网格图游走上的思路。
从 $(0, 0)$ 向 $(n, n)$ 走，每次从主对角线出发乘上额外的系数 $\frac{c}{c-1}$ 。
为了后文描述简洁，记卡特兰数生成函数为 $C(x) = 1 + x + 2x^2 + 5x^3 + 14x ^ 4 \cdots$
考虑枚举从主对角线出发的次数 $k$，那么就有

$$ans = \sum_{k=1}^n[x^{n-k}]C^k(x) * c^k * (c-1) ^ {n-k}$$

之后再设法处理 $[x ^ n] C ^{k} (x)$ 这样的东西。
结论是

$$[x ^ n] C ^ {k} (x) = \binom{2n + k - 1}{n} - \binom{2n + k - 1}{n - 1}$$ ，酷似 Catalan Number，为什么呢？
记 $m = k - 1$，可以在以下两项内容之间双射：

• $[x ^ n] C ^ {m + 1} (x)$
• 长度为 $2n+m$ 的合法括号串，满足前 $m$ 个的字符均为左括号

原因是：$m$ 个 $($ 开头会产生 $k = m + 1$ 段合法括号小段，举个例子：

m = 3， (((1)2)3)4)， 其中 1, 2, 3, 4 的位置均是任意合法括号串。

双射之后的答案可以用折线法计算，不再详述。

然后扫一遍 $k$ 即可，复杂度 $O(n)$。