题目大意：
Problem Description 小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!
解题思路：
看了一下数据，再加上有点感觉是catalan,发现原来是catalan的2倍，嘿嘿，就用catalan大数求了一下。后来看了题解，才发现原来还可以递推，只是，catalan数达到了35的两倍，恐怕__int64也只能刚刚好容下吧，好吧，有些题还真是得试试才知道。
递推代码：
#include
using namespace std;
const int MAX = 36;
int main(void)
{
int n, cas_c = 1;
__int64 f[MAX][MAX];
memset(f, 0, sizeof(f));
f[0][0] = 1;
while(scanf("%d", &n), n >= 0)
{
for(int i = 1; i <= n; i++)
{
f[i][0] = f[i-1][0];
for(int j = 1; j < i; j++)
{
f[i][j] = f[i][j-1] + f[i-1][j];
}
f[i][i] = f[i][i-1];
}
printf("%d %d %I64d\n", cas_c++, n, 2 * f[n][n]);
}
return 0;
}
代码：
catalan大数运算：
//h(n)=h(n-1)*(4*n-2)/(n+1); h(0) = 1;
#include
using namespace std;
const int MAX_LEN = 10005;
const int MAX_NUM = 36;
int catalan[MAX_NUM][MAX_LEN];
void multip(int *cata, int b, int &len)
{
int carry = 0;
for(int i = 0; i < len; i++)
{
int temp = cata[i] * b + carry;
cata[i] = temp % 10;
carry = temp / 10;
}
while(carry)
{
len++;
cata[len-1] = carry % 10;
carry /= 10;
}
return ;
}
void division(int *cata, int b, int &len)
{
int r = 0;
for(int i = len-1; i >= 0; i--)
{
int temp = cata[i] + r * 10;
cata[i] = temp / b;
r = temp % b;
}
while(!cata[len-1])
{
len--;
}
return ;
}
int main(void)
{
int len[MAX_NUM];
memset(catalan, 0, sizeof(catalan));
memset(len, 0, sizeof(len));
catalan[0][0] = 1;
len[0] = 1;
for(int i = 1; i < MAX_NUM; i++)
{
memcpy(catalan[i], catalan[i-1], sizeof(catalan[i-1]));
len[i] = len[i-1];
multip(catalan[i], 4*i-2, len[i]);
division(catalan[i], i+1, len[i]);
}
//for(int i = 0; i < 20; i++)
//{
// for(int j = len[i]-1; j >= 0; j--)
// {
// printf("%d", catalan[i][j]);
// }
// printf("\n");
//}
int n, cas_c = 1;
while(scanf("%d", &n), n >= 0)
{
multip(catalan[n], 2, len[n]);//卡特兰数的两倍
printf("%d %d ", cas_c++, n);
for(int i = len[n]-1; i >= 0; i--)
{
printf("%d", catalan[n][i]);
}
printf("\n");
}
return 0;
}