HDU 3723 Delta Wave（组合计数，卡特兰数）

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

题目：从坐标系的第一象限，0，0点到n,0点，不能到x轴以下，每次y值差值最大为1，也就是要么加1，要么减1，要么不变。问有多少种

http://acm.hdu.edu.cn/showproblem.php?pid=3723

其实是一个水题嘛

枚举有多少个0。剩下的-1，1的个数一样，而且要不能为负，显然是个卡特兰数

枚举0或者枚举1是一样的， 枚举有i个1，那么肯定有i个-1，剩下的为0，则C(n,2*i)*卡特兰(i)

但是这样复杂度略高，预处理卡特兰数是O(n)没问题，但是还有个组合数，大概为n^2的复杂度。

这里可以有一个递推，用CAN表示卡特兰数

C(n,2*(i+1))*CAN(i+1)=(n-2*i)*(n-2*i-1)/(i+1)/(i+2) * (C(n,2*i)*CAN(i))。这样就可以递推，O(n)求出了

其实是很少写JAVA，贴个代码，以上描述很渣，请无视

import java.util.*;import java.math.*;public class Main{public static void main(String[] args){Scanner cin = new Scanner(System.in);while(cin.hasNext()){int n;n=cin.nextInt();BigInteger ans=BigInteger.ONE;BigInteger tmp=BigInteger.ONE;for(int i=0;i<n/2;i++){tmp=tmp.multiply(BigInteger.valueOf(n-2*i)).multiply(BigInteger.valueOf(n-2*i-1)).divide(BigInteger.valueOf(i+1)).divide(BigInteger.valueOf(i+2));ans=ans.add(tmp);}ans=ans.mod(BigInteger.TEN.pow(100));System.out.println(ans);}}}