P1976 鸡蛋饼（JAVA题解）

洛谷P1976鸡蛋饼（JAVA题解）

• • 题目背景
  • 题目描述
  • 输入格式
  • 输出格式
  • 输入输出样例
  • • • 输入
      • 输出

原题链接: 鸡蛋饼

题目背景

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;
    }
}