JS's Blog
0%

Hdu 2067 小兔的棋盘 （卡特兰数）

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2067、
题目大意：
一个大小为n∗nn*n的棋盘，从左下角走到右下角，每次只能向上或者向右走，不能穿越对角线，一共有多少种走法
分析：
先考虑右下三角的情况，最后总数乘2即可
http://blog.sina.com.cn/s/blog_6aefe4250101asv5.html
http://www.cnblogs.com/wuyuegb2312/p/3016878.html#suggestion
http://blog.sina.com.cn/s/blog_4298002e0100eko0.html
几篇关于卡特兰数详细解释的博客
我的理解，卡特兰数主要用于解决，一个变量被另一个变量限制的问题，比如：
括号匹配，有一个右括号必然之前要有一个左括号，即在放下一个右括号之前，序列中的左括号数必须大于右括号数
再或者公园找零问题
2n个人排队买票，其中n个人持50元，n个人持100元。每张票50元，且一人只买一张票。初始时售票处没有零钱找零。请问这2n个人一共有多少种排队顺序，不至于使售票处找不开钱？
若想找的开钱，那在收100元之前，已收50元的数目必须大于100元的数目
再比如当前的问题
若要不穿越对角线，则向上走的步数必须时刻小于等于向右走的步数
第一步一定向右走，假设第k步向上走，一共要走2n2n步，同时2 k−12~k-1且k+1 2nk+1~2n也满足这个性质
卡特兰数主要有几个式子可求

h(n)=C2nnn+1h(n) = \frac{C_{2n}^n}{n+1}

h(n)=C2nn−C2nn−1h(n) = C_{2n}^n - C_{2n}^{n-1}

h(n)=h(0)∗h(n−1)+h(1)∗h(n−2)+⋯+h(n−1)∗h(0)h(n) = h(0)*h(n-1) + h(1)*h(n-2)+\cdots+h(n-1)*h(0)

这题不能使用第一二个公式，因为n≤35n\leq35过于大，C7035C_{70}^{35}的值会爆longlong 所以使用第三个公式打表即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
#include <algorithm>
#define mod 1000000007
using namespace std;
typedef long long ll;
ll ctl[109]={1,1};
void init()
{
    for (int i = 1 ; i <= 36 ; i ++)
    {
        ctl[i]=0;
        for (int j = 0 ; j < i ; j ++)
            ctl[i]+=ctl[j]*ctl[i-j-1];
    }

}

int main()
{
    init();
    int n,ca=1;
    while (~scanf("%d",&n))
    {
        if (n==-1)
            break;
        printf("%d %d %I64d\n",ca++,n,2*ctl[n]);
    }
}