HDU 4828

其实。。这题是《组合数学》的习题中的一道。。。。。。当初不会。。。。。

想到一个证明：

填入2n个数，把填在上方的数的位置填上+1，下方的填上-1。这样，在序列1....2n的位置，任意前部分和都是>=0且是符合题意的。为什么？首先，可以知道，按+1/-1的位置按顺序在上方或下方填数，必定是符合递增的。其次，是否存在不符合部分和>=0而又满足题意的呢？不妨设最小不符合部分和的数为k，则k必在下方。那么，必定要在它的上方填上一个比它小的赋为+1值的位置的数吧。而前k-1个数必为偶数，又因为要满足递增要求，必定是刚好填满两行的前（k-1）/2个格子，这样，就找不到可以填在k上方的数了。所以，任意前部分和都是>=0且是符合题意的。

所以，这个数必定是卡特兰数。

事后诸葛亮了一把。。。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL __int64
#define M 1000000007
#define N 1000000
using namespace std;

LL Cata[N+1];

void exgcd(__int64 a,__int64 b,__int64 &x,__int64 &y){
    if(b==0){
        x=1; y=0;
        return ;
    }
    exgcd(b,a%b,x,y);
    __int64 t=x;
    x=y;
    y=t-a/b*y;
}

void initial(){
	Cata[1]=1;
	LL x,y;
	for(int i=2;i<=N;i++){
		Cata[i]=(Cata[i-1]*(4*i-2))%M;
		exgcd(i+1,M,x,y);
		Cata[i]=((Cata[i]*((x%M+M)%M))%M+M)%M;
	}
}

int main(){
	LL n;int T,kase=0;
	initial();
	scanf("%d",&T);
	while(T--){
		scanf("%I64d",&n);
		printf("Case #%d:
",++kase);
		printf("%I64d
",Cata[n]);
	}
	return 0;
}