加入收藏 | 设为首页 | 会员中心 | 我要投稿 核心网 (https://www.hxwgxz.com/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

hdu 1023Catalan出栈方案+大数

发布时间:2021-01-19 13:23:43 所属栏目:大数据 来源:网络整理
导读:点击打开链接 Catalan //入栈顺序递增1...n 求出栈方式有多少种 //对编号1进行分类 编号1为出栈序列的第k个元素 //则方案为f(k-1)*f(n-k) k从1累加到n,母函数求递推公式得到 f[n]=f(n-1)*(4n-2)/(n+1)? #include iostream#include cstdio#include cstring#in

点击打开链接

Catalan

//入栈顺序递增1...n 求出栈方式有多少种
//对编号1进行分类 编号1为出栈序列的第k个元素
//则方案为f(k-1)*f(n-k) k从1累加到n,母函数求递推公式得到 f[n]=f(n-1)*(4n-2)/(n+1)?

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue> 
#include <stack>
using namespace std;
typedef long long ll;
const int N=1e2+10;
//入栈顺序递增1...n 求出栈方式有多少种
//对编号1进行分类 编号1为出栈序列的第k个元素
//则方案为f(k-1)*f(n-k) k从1累加到n,母函数求递推公式得到 f[n]=f(n-1)*(4n-2)/(n+1) 
ll f[N][N];//Catalan数  
void Catalan()
{
	f[1][0]=1;//f[i][0]为位数 
	f[1][1]=1;
	f[2][0]=1;
	f[2][1]=2;
	int len=1;
	for(int i=3;i<=100;i++)
	{
		int r=0;//进位
		for(int j=1;j<=len;j++)//大数乘法 
		{
			int t=(f[i-1][j]*(4*i-2))+r;
			r=t/10;
			f[i][j]=t%10;
		}
		while(r)
		{
			f[i][++len]=r%10;
			r/=10;	
		} 
		int yu=0;//余数 
		for(int j=len;j>=1;j--)//大数除法
		{
			int t=f[i][j]+yu*10;
			f[i][j]=t/(i+1);
			yu=t%(i+1);
		} 
		while(!f[i][len])//去掉前导0 
		len--;
		
		f[i][0]=len;
	}
}
int main()
{
	int n;
	Catalan(); 
	while(cin>>n)
	{
		int len=f[n][0];
		for(int i=len;i>=1;i--)
		{
			cout<<f[n][i];
		}
		cout<<endl; 
	}
	return 0;
}

(编辑:核心网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    热点阅读