其实。。这题是《组合数学》的习题中的一道。。。。。。当初不会。。。。。
想到一个证明:
填入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:\n",++kase);
printf("%I64d\n",Cata[n]);
}
return 0;
}