10.5 T2 卡特兰数

对给定的 n，求出有多少个长度为 2n 的序列满足以下条件： 存在一种划分方式，使得将序列按此方式划分成两个不相交的序列以后，所得的两个序列均为 1 到 n 这 n 个整数从小到大排列的结果。 比如考虑 n=3 的情况，对于序列 1 1 2 2 3 3，分别取奇数位和偶数位上的数，即可划分成 2 个不相交的 1 2 3 序列， 对序列 1 2 1 3 2 3，取第 1,2,4 位和 3,5,6 位上的数也可以得到两个不相交的 1 2 3 序列，而序列 1 2 2 3 1 3则不能划分为两个不相交的 1 2 3 序列。 由于结果可能过大，你只需要输出其模 1000000007 的值 Solution： 题初看复杂，但因为只能用两个 1-n 的序列来拼插，所以我们考虑采用动态规划/递推， 假如两个序列中的两个 1 是不同的，两个 2 也是不同的，一直到 两个 n 也是不同的，那么记 f[i][j]表示能拆成第一个序列的前 i 个数，第二个序列的前 j 个数的，长度为 i+j 的序列的个数， 那么显然f[i][j]=f[i-1][j]+f[i][j-1]; 这就是组合数的递推公式，我们所求的 f[n][n]=C(2n,n)（C 为组合数） 而现在是两个相同序列的拼插，由对称性，我们不妨在以上递推中要求每个状态均有 i>=j 来避免数字重复的问题， 于是我们就得到了一个 O(n²)的算法，对任意一个 n，答案就是 f[n][n]，注意到在一次 O(n²)的递推处理后即可单次O(1)回答所有的询问，因此该算法足以通过前 6 个测试点。 稍有数学感觉的人即可看出，答案相当于从网格坐标系 中(0,0)点走到(n,n)点， 并且路线始终在连接两点线段的下 方（含线段）的路线方案。 而这个方案数便为 Catalan 数， 也即(2n)!/(n!(n+1)!) 因此我们只要获得n!在模mod=1000000007下的乘法逆 元（记为 r）来进行模意义下的除法（对 a 在模 mod 意义下除 n!等价于模意义下求 a*r）， 而 mod 是一个质数，由费马小定理有(n!)^(mod-2)*(n!)≡1，则 r=(n!)^(mod-2)便是 n!在 mod 下的乘法逆元，使用快速幂求出即可。 PS：考试时推出来了（想到栈排序） 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) h(n)=h(n-1)*(4*n-2)/(n+1); 常见卡特兰数 A.括号化 矩阵连乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种) B.出栈次序 一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列? 首先，我们设f（n）=序列个数为n的出栈序列种数。 （我们假定，最后出栈的元素为k，显然，k取不同值时的情况是相互独立的， 也就是求出每种k最后出栈的情况数后可用加法原则，由于k最后出栈，因此，在k入栈之前，比k小的值均出栈，此处情况有f(k-1)种，而之后比k大的值入栈，且都在k之前出栈，因此有f(n-k)种方式，由于比k小和比k大的值入栈出栈情况是相互独立的，此处可用乘法原则，f(n-k)*f(k-1)种，求和便是Catalan递归式。） 类似问题 买票找零 有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少种方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈) C.凸多边形三角划分 类似问题 一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？ 在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数？ D.给定节点组成二叉搜索树 给定N个节点，能构成多少种不同的二叉搜索树？ （能构成h（N）个）(这个公式的下标是从h(0)=1开始的） E. n对括号正确匹配数目 给定n对括号，求括号正确配对的字符串数， 例如： 0对括号：[空序列] 1种可能 1对括号：() 1种可能 2对括号：()() (()) 2种可能 3对括号：((())) ()(()) ()()() (())() (()()) 5种可能 那么问题来了，n对括号有多少种正确配对的可能呢？ 考虑n对括号时的任意一种配对方案，最后一个右括号有唯一的与之匹配的左括号， 于是有唯一的表示A(B)，其中A和B也是合法的括号匹配序列。 假设S(n)为n对括号的正确配对数目，那么有递推关系S(n)=S(0)S(n-1)+S(1)S(n-2) +...+S(n-1)S(0)，显然S(n)是卡特兰数