bzoj 3907: 网格 （卡特兰数+组合数学+高精度）

Description

Input

输入文件中仅有一行，包含两个整数n和m，表示城市街区的规模。

Output

输出文件中仅有一个整数和一个换行/回车符，表示不同的方案总数。

Sample Input

Sample Output

HINT

Source

题解：卡特兰数+组合数学+高精度

这道题相当于经典的购票问题。

最后的答案是C(n+m,n)-C(n+m,n+1)

这里有一些有关卡特兰数问题的讲解：http://blog.csdn.net/wuyuegb2312/article/details/9339529 

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define N 10003using namespace std;struct data {	int s[N],len;	data (){		memset(s,0,sizeof(s));		len=0;	}}ans,ans1;int n,m,PRime[N],mp[N],pd[N],num[N];void init(){	for (int i=2;i<=10000;i++) {		if (!pd[i]) prime[++prime[0]]=i,mp[i]=prime[0];		for (int j=1;j<=prime[0];j++) {			if (prime[j]*i>10000) break;			pd[prime[j]*i]=1;			if (i%prime[j]==0) break;		}	}}void calc(int x,int val){	int k=x;	for (int i=1;prime[i]*prime[i]<=k;i++) 	 if (k%prime[i]==0) {	 	while (k%prime[i]==0) 	 	 num[i]+=val,k/=prime[i];	 }	if (k>1) num[mp[k]]+=val;}data mul(data a,int x){	data c; int t=a.len;	for (int i=1;i<=a.len;i++) 	 c.s[i]=a.s[i]*x;	for (int i=1;i<=t;i++) {		c.s[i+1]+=c.s[i]/10;		c.s[i]%=10;	}	while (c.s[t+1]) {		t++; c.s[t+1]+=c.s[t]/10;		c.s[t]%=10;	}	c.len=t;	return c;}data jian(data a,data b){	data c;	int t=a.len;	for (int i=1;i<=t;i++) c.s[i]=a.s[i]-b.s[i];	for (int i=1;i<=t;i++) 	 if (c.s[i]<0) c.s[i]+=10,c.s[i+1]--;	while (!c.s[t]) t--;	c.len=t;	return c; }int main(){	freopen("a.in","r",stdin);	freopen("my.out","w",stdout);	scanf("%d%d",&n,&m);	init();	for (int i=n+1;i<=n+m;i++) calc(i,1);	for (int i=1;i<=m;i++) calc(i,-1);	ans.len=ans.s[1]=1;	for (int i=1;i<=prime[0];i++) 	 while (num[i]) ans=mul(ans,prime[i]),num[i]--;	//for (int i=ans.len;i>=1;i--) printf("%d",ans.s[i]);	//printf("/n");	for (int i=m;i<=n+m;i++) calc(i,1);	for (int i=1;i<=n+1;i++) calc(i,-1);    ans1.len=ans1.s[1]=1;	for (int i=1;i<=prime[0];i++) 	 while (num[i]) 	  ans1=mul(ans1,prime[i]),num[i]--;	//for (int i=ans1.len;i>=1;i--) printf("%d",ans1.s[i]);	//printf("/n");	ans=jian(ans,ans1);	for (int i=ans.len;i>=1;i--) printf("%d",ans.s[i]);	printf("/n");}