原题链接: 鸡蛋饼
题目背景
Czyzoiers 都想知道小 x 为什么对鸡蛋饼情有独钟。经过一番逼问，小 x 道出了实情：因为他喜欢圆。
题目描述
最近小 x 又发现了一个关于圆的有趣的问题：在圆上有 2N2N 个不同的点，小 x 想用 N 条线段把这些点连接起来（每个点只能连一条线段）， 使所有的线段都不相交，他想知道这样的连接方案有多少种？
输入格式
有且仅有一个正整数 N 。 （N \le 2999N≤2999）
输出格式
要求的方案数（结果 \bmod 100000007mod100000007）。
输入输出样例
输入
24
输出
4057031
晕，同余定理杀我= =。
本题用到卡特兰数+同余定理+扩展欧几里得求逆元。
置于本题为什么要用卡特兰数，可以自己在纸上进行验算，可以看出每次切分鸡蛋饼时，总是将问题划分成两个解决过的子问题，子问题的方案数需要与父问题方案数相乘，符合卡特兰数的递推式。
由于卡特兰定理有多个推导公式，导致本题也可以使用多种做法：
法1：直接使用递推解，C表示组合数
f(n) = C(2n,n)/(n+1)
法2：使用递推公式：
f(n)= f(0)*f(n-1)+f(1)*f(n-2) + ··· + f(n-1)*f(0)
法3：使用递推公式的结论：
f(n)=(4n+2)/(n+2)*f(n)
在这里我给出法三的解法，其余的解法相似，如果你不会扩展欧几里得求逆元或者懒得管余数，大可以使用python(人生苦短)，只需要在结果处取余即可。
代码如下，需要注意的是取余的部分，涉及到除法同余，要利用扩展欧几里得求逆元。其次，由于涉及到减法同余，还需加MOD进行补齐。
import java.io.*;
// 卡特兰数+同余定理+扩展欧几里得求逆元
public class Main {
static StreamTokenizer cin;
static PrintWriter out;
static int N;
static int MOD = 100000007;
public static void main(String[] args) throws IOException{
cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
out = new PrintWriter(new OutputStreamWriter(System.out));
N = nextInt();
long[] f = new long[N+1];
f[1] = 1;
for(int i = 2; i < N+1; i++){
long[] arr = new long[2];
extendGcd(MOD, i+1, arr);
f[i] = ((((f[i-1]%MOD) * ((4L*i-2)%MOD))%MOD * ((arr[1]+MOD)%MOD)) + MOD)%MOD;
}
out.println(f[N]);
out.flush();
out.close();
}
/**
* 扩展欧几里得算法求逆元：递归计算xa+yb=gcd(a,b)=1
*/
static long extendGcd(long a, long b, long[] r) { // r为二元数组, 代表x, y
if (b == 0) { // 递归边界
r[0] = 1; r[1] = 0;
return a;
} else {
long ans = extendGcd(b, a%b, r);
long t = r[0];
r[0] = r[1];
r[1] = t-(a/b)*r[1];
return ans;
}
}
static int nextInt() throws IOException{
cin.nextToken();
return (int)cin.nval;
}
}
