题解

思路推导

把持 $50$ 元钱币的人记为 A，持 $100$ 元钱币的人记为 B。售票处每收到一张 $50$ 元钱币，零钱数增加一；每接待一名 B，零钱数减少一。队伍合法当且仅当任意前缀中 A 的数量都不少于 B 的数量，并且最终两者都恰有 $n$ 个。

这正是第 $n$ 个 Catalan 数。可以从路径计数理解：从 $(0,0)$ 出发，A 对应向右一步，B 对应向上一步；需要统计不越过对角线且到达 $(n,n)$ 的路径数。

做法

第 $0$ 个 Catalan 数为 $C_0=1$。相邻两项满足

$$C_{k+1}=C_k\cdot\frac{2(2k+1)}{k+2}.$$

从 $C_0$ 开始依次递推到 $C_n$ 即可。每一步的结果都是整数。$n\le20$ 时，最大答案为 $C_{20}=6564120420$，需要使用 64 位整数。

正确性证明

合法队伍与从 $(0,0)$ 到 $(n,n)$ 且不越过对角线的格路一一对应：读到 A 时向右，读到 B 时向上；“任意时刻有零钱”恰好等价于任意前缀中 A 不少于 B，也就是路径不越过对角线。

由反射原理，所有从 $(0,0)$ 到 $(n,n)$ 的路径有 $\binom{2n}{n}$ 条，越过对角线的路径有 $\binom{2n}{n-1}$ 条。因此合法路径数为

$$\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}=C_n.$$

所用递推式由相邻 Catalan 数的闭式之比直接得到，所以算法输出的正是合法队伍数量。

复杂度分析

时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。