题意：从坐标（0， 0）到（n， 0）的折线，这条折线每向右延伸一个单位长度，高度要么不变，要么+1，要么-1，（不能到y=0以下）已知n，求这种折线种数

思路：我们知道上升和下降的次数要一样，而这就像卡特兰数的入栈出栈次序一样，所以我们从n中选出2k次进行类出栈模拟，
那么ans[k] = C[n][2k]*C[2k][k]/(k+1)，计算组合数n^2会T，然后我们可以相除ans[k-1] = C[n][2k-2]*C[2k-2][k-1]/(k)

两式递推出结果是ans[k] = ans[k-1]*(n-2*k+2)*(n-2*k+1)/(k*(k+1)) 

import java.math.BigInteger;
import java.util.Scanner;


public class Main {

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

}

Delta Wave
Time Limit: 6000/3000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1230????Accepted Submission(s): 398



  
  Problem Description
 
 
 
 

  
  A delta wave is a high amplitude brain wave in humans with a frequency of 1 – 4 hertz which can be recorded with an electroencephalogram (EEG) and is usually associated with slow-wave sleep (SWS).
  
  
-- from Wikipedia
  
  

The researchers have discovered a new kind of species called "otaku",whose brain waves are rather strange. The delta wave of an otaku's brain can be approximated by a polygonal line in the 2D coordinate system. The line is a route from point (0,0) to (N,0),and it is allowed to move only to the right (up,down or straight) at every step. And during the whole moving,it is not allowed to dip below the y = 0 axis.
  
  

For example,there are the 9 kinds of delta waves for N = 4:
  
  


 
   


  
  


Given N,you are requested to find out how many kinds of different delta waves of otaku.
 
 
 
 

  
  ?
 
 


  
  Input
 
 
 
 

  
  There are no more than 20 test cases. There is only one line for each case,containing an integer N (2 < N <= 10000)
  
  



 
 

  
  ?
 
 


  
  Output
 
 
 
 

  
  Output one line for each test case. For the answer may be quite huge,you need only output the answer module 10
  
  100.
 
 
 
 

  
  ?
 
 


  
  Sample Input
 
 
 
 

  
  
   
   

    
    3
4
   
   
 
 
 
 

  
  ?
 
 


  
  Sample Output
 
 
 
 

  
  
   
   

    
    4
9