首页 > 代码库 > HDU 4828

HDU 4828

2024-07-26 07:35:16   215人阅读

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

想到一个证明：

填入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 1000000using 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;}

　　

HDU 4828


联系
我们