卡特兰数

小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!
Input
每次输入一个数n(1<=n<=35)，当n等于－1时结束输入。
Output
对于每个输入数据输出路径数，具体格式看Sample。
Sample Input
1
3
12
-1
Sample Output
1 1 2
2 3 10
3 12 416024

分析：这一题n不是很大，所以可以用第一种的递推式来写，这样反而不会溢出

#include<bits/stdc++.h>
using namespace std;
long long c[40];
int main()
{
    c[0]=1;c[1]=1;
    for(int i=2;i<=35;i++){
        for(int j=0;j<i;j++)
        {
            c[i] += c[j] * c[i-j-1];
        }
    }
    int n,num=1;
    while(cin >>n){
        if(n == -1) break;
        printf("%d %d %lld\n",num++,n,c[n]*2); 
    }
    return 0;
}

此时n等于100：当n很大时：64位已经不能表示了，可以把一个一个数放进数组里，再根据运算法则处理数据，最后输出想要的答案

//推导公式： h(n)=h(n-1)*(4*n-2)/(n+1);
#include<iostream>  
using namespace std;  
int a[101][101]={0};  
int main()  
{  
    int n,i,j,len,r,temp,t;  
    int b[101];        //标记长度 
    a[1][0] = 1;  
    len = 1;  
    b[1] = 1;  
    for(i=2;i<=100;i++)  
    {    
        for(j=0;j<len;j++) //乘法  
            a[i][j] = a[i-1][j]*(4*i-2);  
        for(r=j=0;j<len;j++)  //处理相乘结果（从后往前为 个，十，百，千，万……） 
        {  
            temp = a[i][j] + r;  
            a[i][j] = temp % 10;  
            r = temp / 10;  
        }  
        while(r) //进位处理  
        {  
            a[i][len++] = r % 10;  
            r /= 10;  
        }  

        for(j=len-1,r=0;j>=0;j--) //除法  
        {  
            temp = r*10 + a[i][j];  
            a[i][j] = temp / (i+1);  
            r = temp % (i+1);  
        }  
        while(!a[i][len-1]) //高位零处理  
            len --;  
        b[i] = len;  
    }  
    while(cin>>n)  
    {     
        for(j=b[n]-1;j>=0;j--)  
            printf("%d",a[n][j]);  
        printf("\n");  
    }  
    return 0;  
}

当n大，但是有取模要求时：运用拓展欧几里得，求逆元等知识来除法取模。

//推导公式：h(n)=h(n-1)*(4*n-2)/(n+1); 
//因为有取模，所以可以用long long 不会超限 
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1000005;
const long long MOD = 1000000007;

long long extend_gcd(long long a,long long b,long long &x,long long &y)  
{
    if(a == 0 && b == 0) return -1;
    if(b == 0){
        x = 1; y = 0; 
        return a;
    }
    long long d = extend_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

long long mod_reverse(long long a, long long n) //求逆元 
{
    long long x,y;
    long long d = extend_gcd(a, n, x, y);
    if(d == 1) return (x % n + n) % n;
    else return -1;
}
long long C[N];
int main() {
    C[1] =1; C[2] = 1;
    for (int i = 2; i < N; i++) {
        long long tmp = mod_reverse((long long) i, MOD);      
        C[i] = C[i - 1] * (4 * i - 6) % MOD * tmp % MOD;  //除法取模
    }
    int ans = 1,t,n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        printf("Case #%d:\n", ans++);
            printf("%lld\n", C[n+1]);
    }
    return 0;
}