Contset Hunter 1102 高精度求卡特兰数

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

用递推的方式写的写挂了，而如果用组合数又不会高精度除法，偶然看到了别人的只用高精度乘低精度求组合数的方法，记录一下

#include<bits/stdc++.h>

using namespace std;

const int maxn=60010;

const long long M=1000000000;

typedef long long LL;

LL num[maxn];

int cnt[maxn*2];//记录素数因子的个数

int len=1;

void get_cnt(int x,int y){

	for(int i=2;i*i<=x&&x>1;i++){

		while(x%i==0){

			x/=i;

			cnt[i]+=y;

		}

	}

	if(x)cnt[x]+=y;

}

void mul(LL x){//高精度乘单精度

	for(int i=1;i<=len;i++)

		num[i]*=x;

	for(int i=1;i<=len;i++){

		num[i+1]+=(num[i]/M);

		num[i]%=M;

	}

	while(num[len+1])len++;

}

int main(){

	int n;

	scanf("%d",&n);

	num[1]=1;

	for(int i=n+1;i<=n*2;i++)//乘法就是加素数因子的个数

		get_cnt(i,1);

	for(int i=2;i<=n+1;i++)//除法就是减素数因子的个数

		get_cnt(i,-1);

	for(LL i=2;i<=2*n;i++)//求的时候只关心素数因子剩多少个就行了

		for(LL j=1;j<=cnt[i];j++){

			mul(i);

		}

	printf("%lld",num[len]);

	for(int i=len-1;i>0;i--)

		printf("%09lld",num[i]);

}