模型一：进出序列。

求解：给定n个的数，有多少种出栈序列？(抽象成一个有n个1和n个-1组成的字串，且前k个数的和均不小于0，那这种字串的总数为多少？)

容斥可得 ans(合法) = ans(all) - ans(不合法)
ans(all) = C(2n,n) //任选n个位置放1.

首选，我们将这个字符串看成二进制，那么对于每个不合法的方案数，一定是前缀和 = -1的第一个位置，也就是2 * m + 1的位置处是-1.

前面m个1，m个-1.那么剩下(2 * n - (2 * m + 1)) = 2 * (n - m) - 1个位。

我们将这些位都翻转，可得这个字符串由n + 1个 - 1和n - 1个1组成，并且我们可以发现，对于由(n + 1)个-1和(n - 1)个+1组成的字符串，一定都存在前缀和 -1的第一个位置，我们将剩下的位置反转。

就都对应着n 个 1和n 个 -1组成的不合法字符串，所以对于所有(n + 1)个-1和(n - 1)个1组成的字符串，都对应着n 个 1和n 个 -1组成的不合法字符串.

所以ans(不合法) = C(2n,n + 1)//任选n + 1个位置放-1.

所以ans(all) = C(2n,n) - C(2n,n + 1) = C(2n,n) / (n + 1).