题意：给定2行n列的长方形，然后把1—2*n的数字填进方格内，保证每一行，每一列都是递增序列，求有几种放置方法,对1000000007取余；
思路：本来想用组合数找规律，但是找不出来，搜题解是卡特兰数，而且还有一个难点在于N的范围是1000000，卡特兰数早已数千位，虽然有取余；
解决方法就是用在求卡特兰数的时候快速取余+带模除法；
卡特兰数递归公式1：K(n)=K(n-1) * ((4*n-2)/(n+1)); 组合数公式2：K[n] = C[2*n][n] /(n+1);
看公式1，有个除法运算，K(n-1) * ((4*n-2)很大，无法直接求得K(n-1) * ((4*n-2)/(n+1))的值，因此需要求乘法逆元（满足a*k≡1 (mod p)的k值就是a关于p的乘法逆元，按 照倒数理解就好）；
求乘法逆元的方法：扩展欧几里得，费马小定理；
1 ///扩展欧几里得 2 typedef long long LL ; 3 LL exgcd(LL a,LL b,LL &x,LL &y)///使得ax+by==gcd(a,b); 4 { 5 if( b == 0 ) 6 { 7 x = 1; 8 y = 0; 9 return a; 10 } 11 else 12 { 13 LL x1,y1; 14 LL d = exgcd ( b , a % b , x1 , y1 ); 15 x = y1; 16 y= x1 - a / b * y1; 17 return d; 18 } 19 }
费马小定理说，对于素数 M 任意不是 M 的倍数的 b，都有：
b ^ (M-1) = 1 (mod M)
于是可以拆成：
b * b ^ (M-2) = 1 (mod M)
于是：
a / b = a / b * (b * b ^ (M-2)) = a * (b ^ (M-2)) (mod M)
也就是说我们要求的逆元就是 b ^ (M-2) (mod M)；
1 long long C[1000005] = {0LL}; 2 long long spow(long long x, int n)///递归 3 { 4 if (n == 1) 5 return x; 6 else 7 { 8 long long v = spow(x, n/2); 9 if (n%2 == 0) 10 return v*v%MODLL; 11 else 12 return v*v%MODLL*x%MODLL; 13 } 14 }
补充一下卡特兰数的应用（无特别说明答案都是 K（n））：
- 括号化问题：P=a1*a2*a3*…*an,依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方法。
- 有n个节点的二叉树共有多少种情形？
- 一个栈（无穷大）的进栈序列为1,2,3，…,n，有多少个不同的出栈序列？
- 买票找零问题： 球票为50元，有2n个人排除买票，其中n个人手持50元的钞票，n个人持100元的钞票，假设售票处无零钱，问这2n个人有多少种排列方式，不至于使售票处出现找不开钱的局面。
- 凸多边形的三角剖分问题：求将一个凸多边形区域分成三角形区域的方法数。对于有n条边（n+1个顶点）的多边形的一个三角剖分与具有n-1个叶节点的分析树对应。所以，由n+1个顶点n条边构成多边形的三角剖分数目为h(n-2).
- 上班路径问题一位律师在住所以北n个街区和以东n个街区工作。每天她走2n个街区去上班。如果她不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
- 圆上的点连线问题---在圆上选择2n个点，将这些点成对连接起来使得所得到的n条线段不相交的方法数？