算法

(卡特兰数通项公式)

f(n) = 1 / (n + 1) * (2n)! / n!
注意n最大为5000，所以long类型不work，需要用BigInteger。

时间复杂度 $O(n)$

参考文献

http://data.biancheng.net/view/35.html
https://www.cnblogs.com/hujunzheng/p/5040334.html
https://blog.csdn.net/adminabcd/article/details/46672759

Java 代码

import java.io.*;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        BigInteger total = combination(2 * n, n);
        total = total.divide(new BigInteger(Integer.toString(n + 1)));
        System.out.println(total);
    }

    private static BigInteger combination(int m, int n) {
        m = m - n + 1;
        BigInteger total = new BigInteger("1");
        for (int i = 1; i <= n; i++) {
            total = total.multiply(new BigInteger(Integer.toString(m)));
            m++;
            total = total.divide(new BigInteger(Integer.toString(i)));
        }
        return total;
    }
}