洛谷 P2532 [AHOI2012]树屋阶梯（高精度卡特兰数）
传送门
需要注意只能使用n个钢材，那么意味着每一个对角对应的矩形是唯一的，不可再分割成更小的矩形，如图所示：
那么我们不难得到如下递推式：
f ( n ) = ∑ i = 0 n − 1 f ( i ) ∗ f ( n − i − 1 ) f(n)=\sum_{i=0}^{n-1} f(i)*f(n-i-1) f(n)=∑i=0n−1f(i)∗f(n−i−1)
那么就是卡特兰数了，因为涉及到高精度，所以要 J a v a Java Java
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
static BigInteger f[]=new BigInteger[1005];
public static void main(String[] args) {
// TODO Auto-generated method stub
int n;
Scanner scanner = new Scanner(System.in);
n=scanner.nextInt();
f[2] = BigInteger.ONE;
BigInteger four=BigInteger.valueOf(4);
BigInteger six =BigInteger.valueOf(6);
for(int i=2;i<n+2;i++) {
BigInteger j=BigInteger.valueOf(i);
f[i+1]=four.multiply(j).subtract(six).multiply(f[i]).divide(j);
}
System.out.println(f[n+2]);
}
}