UVA - 1478 Delta Wave （大數+卡特蘭數）

UVA - 1478 Delta Wave （大數+卡特蘭數）

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 < N10000)

Output

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

Sample Input

3 
4

Sample Output

4 
9
題意：從坐標（0， 0）到（n， 0）的折線，這條折線每向右延伸一個單位長度，高度要麼不變，要麼+1，要麼-1，已知n，求這種折線種數
思路：我們知道上升和下降的次數要一樣，而這就像卡特蘭數的入棧出棧次序一樣，所以我們從n中選出2k次進行類出棧模擬，
那麼ans[k] = C[n][2k]*C[2k][k]/(k+1)，然後我們可以相除兩式遞推出結果是ans[k] = ans[k-1]*(n-2*k+2)*(n-2*k+1)/(k*(k+1)) 
import java.io.*;
import java.util.*;
import java.math.*;

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