卡特兰数

今天有点人品，T1的50pts暴力怒压正解。。这数据。。不言而喻 $\text{score: 100 + 0 + 0 = 100 rk: 7/36}$ Problem A：时间管理带师题目描述众所周知，罗老师是时间管理带师 因为罗老师是时间管理带师，所以他的时间是以东为单位的 具体来讲，罗老师一天有nn东的时间 现在有很多妹子想跟罗老师约会 奇特的，她们每天总会提出两段约会时间（可能相同，代表一种），并且每天提出的总是一样的。 她们提出的约会时间形式形如i,j,代表希望在[i东,(i+1)东)[i东,(i+1)东)或[j东,(j+1)东)[j东,(j+1)东)与罗老师进行约会。 当然，罗老师可以这两段时间都与这个妹子约会,只选择一段，或者伤心地抛弃。 那么，作为时间管理带师的罗老师，每天会选择尽可能多的妹子进行约会 但你一定要注意,罗老师最近并不打算进行多人运动，所以他不会在1东的时间同时与两个或多个妹子约会 罗老师并不脸盲，与一个妹子约会2次并不能算成”2”次的贡献，只能是”1” 罗老师是时间管理带师，只要满足以上条件，他就可以安排好他的时间，不用担心别的 而且,每天可能会有新的 ...

题意将题意转化一下 有 $m = \sum\limits_{i = 1}^n w_i$ 个数，前 $n$ 个中第 $i$ 个为 $w_i − 1$ ，剩下的 $m − n$ 个数都是 $− 1$ 求对这 $m$ 个数 $m!$ 种重排的方案中，有多少种满足重排后的序列任意前缀和不为负 题解卡特兰数的另一种组合意义首先有一个引理 给定 $n$ 个 $1$ 和 $n$ 个 $- 1$，它们组成一个长度为 $2n$ 的序列 $a$，则必定存在一个 $i$ 使得序列 $a_{i + 1…2n} + a_{1…i}$ 满足任意前缀都不小于零 证明也很简单，找到一个使得前缀和最小的位置 $i$，设 $s_{i,j}$ 表示 $a$ 上 $a_i$ 到 $a_j$ 的和，那么显然 $s_{i + 1, 2n} \ge 0$，对 $\forall k \in [1, i]$，$s_{i + 1, 2n} + s_{1, k} \ge 0$ 那么接下来求解 $n$ 个 $1$ 和 $n$ 个 $- 1$ 组成的合法序列（即任意前缀和不小于零）的方案数，也就是卡特兰数 $1$ 的编号为 $1 \sim ...