这道题的地址，想尝试的小伙伴可以来试哦：
https://www.dotcpp.com/oj/problem1163.html
思路：
1. N = K
考虑当 N = K 时的特殊情况，即有 2N 个小孩，其中N个小孩带的钱为1元，另外N个小孩带的钱为2元。
此时可利用卡特兰数的通项公式简单求解:
当然，由于题目中说小孩交换位置算一种新的排队方式，所以还要再乘上 n 的全排列（乘两遍）。
2. N > K
当 N > K 时，无法直接用卡特兰数求解，这时我们可以换一种思维：无法直接求出合法的排队方式数，那就先求出非法的排队方式数，再用总的排队方式数减去，即得合法的排队方式数：
总的排队方式数：
很简单：一共 M 人排队，有 M！（M 的全排列）种排队方式。
非法的排队方式数：
我们考虑一下非法的排队方式有什么特征：
- （1） 前 2P 个小孩组成一个合法的排队，且持有 1 元的小孩和持有 2 元的小孩数量相等，皆为 P。（P = 0, 1, 2……）
- （2） 第 2P 1 个小孩持有 2 元。
证明：
- （1） 证明满足此特征的排队均非法： 显然，由于前 2P 个小孩使得售票员“收支平衡”，第 2P 1 个小孩到来时刚好无钱可找，所以是非法的排队。
- （2） 证明非法的排队均满足此特征：
- 当非法队伍长度为奇数时： <a> 如果除去最后一个孩子仍是非法排队： 去掉队尾一个小孩，进行队伍长度为偶数时的论证。 <b> 如果除去最后一个孩子变为合法排队： ※ 则最后一个孩子一定持有 2 元。（一个合法排队加上一个持有 1 元的小孩并不会变成非法排队） ※ 此合法队列中持有 1 元的小孩和持有 2 元的小孩数量相等。（若持有 2 元的小孩数量较多，此队列一定是非法队列；若持有 1 元的小孩较多，则即便最后一个小孩持有 2 元也不会变为非法队列）
- 当非法队伍长度为偶数时： 则总是存在这样一个正整数 Q（2Q <= 队列长度），使得前 2Q 个小孩构成一非法排队（换言之，如果对于任意的正整数 Q，总有：前 2Q 个小孩构成的队列是合法的，那么这个队列本身也是合法的。） 于是可以对前 2Q 个小孩的非法队列进行递归论证，直到找不到这样的 Q 时，去除队尾一个小孩，进行奇数队伍论证。
计算公式：
非法排队特征：
（1） 前 2P 个小孩组成一个合法的排队，且持有 1 元的小孩和持有 2 元的小孩数量相等，皆为 P。（P = 0, 1, 2……）
（2） 第 2P 1 个小孩持有 2 元。
于是我们可以把非法排队分为 3 部分：
- 前 2P 个小孩
- 第 2P 1 个小孩
- 剩下的小孩，假设共 R 个（R = M - 2P - 1）
前 2P 个小孩组成一个合法排队，且满足：M’ = 2P，N’ = K’ = P。 于是排队数可以用卡特兰数计算。 第 2P 1 个小孩要持有 2 元，由于前 2P 个小孩中已经用掉 P 个持有 2 元的小孩，此处还有 K - P 种选择。 最后 R 个小孩的排队方式不影响整体性质，所以全排列。
公式为：
合法的排队方式数：
合法的排队方法数就等于总的方法数减去非法的方法数：
代码实现：
