hdu 1133（卡特兰数+大数乘除+阶乘）

点击打开链接

卡特兰数的变形

假设m=4,n=3,的一个序列是：0110100显然，它不合法

然后我们把他稍微变化一下：把第一个不合法的“1”后面的所有数0位为1， 1位为0；这样我们得到了另一个序列：0111011，说明每个不合法的都有一个这样的序列跟他一一对应

所以计算公式就是：合法的排列方式=所有排列方式-非法排列方式

这里非法排列方式的计算 就是：(

然而在这题，因为每个人都是不同的，所以还要乘以 M！*N！

所以得出最终方程：

F（N）=(

然后再化简一下;

F(N)=(M+N)! * (M-N+1)/(M+1)

#include"stdio.h"
#include"string.h"
#define N 101
#define B 10000
// *
void mul(int *ans,int b)
{
	int i,t;
	t=0;
	for(i=N-1;i>=0;i--)
	{
		t=t+ans[i]*b;
		ans[i]=t%B;
		t/=B;
	}
}
// /
void div(int *ans,t;
	t=0;
	for(i=0;i<N;i++)
	{
		t=t*B+ans[i];
		ans[i]=t/b;
		t=t%b;
	}
}
// ^
int F[2*N][N];
void fact()
{
	int i;
	F[1][N-1]=1;
	for(i=2;i<=200;i++)
	{
		memcpy(F[i],F[i-1],N*sizeof(int));
		mul(F[i],i);
	}
}

void print(int *ans)
{
	int i;
	i=0;
	while(ans[i]==0&&i<N)i++;
	printf("%d",ans[i++]);
	while(i<N)printf("%04d",ans[i++]);
	printf("n");
}

int main()
{
	int T=1;
	int n,m;
	int ans[N];
	fact();
	while(scanf("%d%d",&m,&n)!=-1&&(n+m))
	{
		printf("Test #%d:n",T++);
		if(m<n)
		{
			printf("0n");
			continue;
		}
		memcpy(ans,F[n+m],N*sizeof(int));//(n+m)!
		mul(ans,m-n+1);
		div(ans,m+1);
		print(ans);
	}
	return 0;
}