Game of Connections
2024-10-14 02:26:30
Game of Connections |
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
Total Submission(s): 856 Accepted Submission(s): 565 |
Problem Description
This is a small but ancient game. You are supposed to write down the numbers 1, 2, 3, ... , 2n - 1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one another. And, no two segments are allowed to intersect.
It's still a simple game, isn't it? But after you've written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right? |
Input
Each line of the input file will be a single positive number n, except the last line, which is a number -1. You may assume that 1 <= n <= 100.
|
Output
For each n, print in a single line the number of ways to connect the 2n numbers into pairs.
|
Sample Input
2 |
Sample Output
2 |
Source
Asia 2004, Shanghai (Mainland China), Preliminary
|
Recommend
Eddy
|
/*
卡特兰数邝斌模板水过........ */
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
/*
* 完全大数模板
* 输出cin>>a
* 输出a.print();
* 注意这个输入不能自动去掉前导0的,可以先读入到char数组,去掉前导0,再用构造函数。
*/
#define MAXN 9999
#define MAXSIZE 1010
#define DLEN 4 class BigNum {
private:
int a[]; //可以控制大数的位数
int len;
public:
BigNum()
{
len=;memset(a,,sizeof(a));
} //构造函数
BigNum(const int); //将一个int类型的变量转化成大数
BigNum(const char*); //将一个字符串类型的变量转化为大数
BigNum(const BigNum &); //拷贝构造函数
BigNum &operator=(const BigNum &); //重载赋值运算符,大数之间进行赋值运算
friend istream& operator>>(istream&,BigNum&); //重载输入运算符
friend ostream& operator<<(ostream&,BigNum&); //重载输出运算符 BigNum operator+(const BigNum &)const; //重载加法运算符,两个大数之间的相加运算
BigNum operator-(const BigNum &)const; //重载减法运算符,两个大数之间的相减运算
BigNum operator*(const BigNum &)const; //重载乘法运算符,两个大数之间的相乘运算
BigNum operator/(const int &)const; //重载除法运算符,大数对一个整数进行相除 运算 BigNum operator^(const int &)const; //大数的n次方运算
int operator%(const int &)const; //大数对一个int类型的变量进行取模运算
bool operator>(const BigNum &T)const; //大数和另一个大数的大小比较
bool operator>(const int &t)const; //大数和一个int类型的变量的大小比较 void print(); //输出大数
};
BigNum::BigNum(const int b) //将一个int类型的变量转化为大数
{
int c,d=b;
len=;
memset(a,,sizeof(a));
while(d>MAXN)
{
c=d-(d/(MAXN+))*(MAXN+);
d=d/(MAXN+);
a[len++]=c;
}
a[len++]=d;
}
BigNum::BigNum(const char *s) //将一个字符串类型的变量转化为大数
{
int t,k,index,L,i;
memset(a,,sizeof(a));
L=strlen(s);
len=L/DLEN;
if(L%DLEN)
len++;
index=;
for(i=L-;i>=;i-=DLEN)
{
t=;
k=i-DLEN+;
if(k<)
k=;
for(int j=k;j<=i;j++)
t=t*+s[j]-'';
a[index++]=t;
}
}
BigNum::BigNum(const BigNum &T):len(T.len) //拷贝构造函数
{
int i;
memset(a,,sizeof(a));
for(i=;i<len;i++)
a[i]=T.a[i];
}
BigNum & BigNum::operator=(const BigNum &n) //重载赋值运算符,大数之间赋值运算
{
int i;
len=n.len;
memset(a,,sizeof(a));
for(i=;i<len;i++)
a[i]=n.a[i];
return *this;
}
istream& operator>>(istream &in,BigNum &b)
{
char ch[MAXSIZE*];
int i=-;
in>>ch;
int L=strlen(ch);
int count=,sum=;
for(i=L-;i>=;)
{
sum=;
int t=;
for(int j=;j<&&i>=;j++,i--,t*=)
{
sum+=(ch[i]-'')*t;
}
b.a[count]=sum;
count++;
}
b.len=count++;
return in;
}
ostream& operator<<(ostream& out,BigNum& b) //重载输出运算符
{
int i;
cout<<b.a[b.len-];
for(i=b.len-;i>=;i--)
{
printf("%04d",b.a[i]);
}
return out;
}
BigNum BigNum::operator+(const BigNum &T)const //两个大数之间的相加运算
{
BigNum t(*this);
int i,big;
big=T.len>len?T.len:len;
for(i=;i<big;i++)
{
t.a[i]+=T.a[i];
if(t.a[i]>MAXN)
{
t.a[i+]++;
t.a[i]-=MAXN+;
}
}
if(t.a[big]!=)
t.len=big+;
else
t.len=big;
return t;
}
BigNum BigNum::operator-(const BigNum &T)const //两个大数之间的相减运算
{
int i,j,big;
bool flag;
BigNum t1,t2;
if(*this>T)
{
t1=*this;
t2=T;
flag=;
}
else
{
t1=T;
t2=*this;
flag=;
}
big=t1.len;
for(i=;i<big;i++)
{
if(t1.a[i]<t2.a[i])
{
j=i+;
while(t1.a[j]==)
j++;
t1.a[j--]--;
while(j>i)
t1.a[j--]+=MAXN;
t1.a[i]+=MAXN+-t2.a[i];
}
else
t1.a[i]-=t2.a[i];
}
t1.len=big;
while(t1.a[len-]== && t1.len>)
{
t1.len--;
big--;
}
if(flag)
t1.a[big-]=-t1.a[big-];
return t1;
}
BigNum BigNum::operator*(const BigNum &T)const //两个大数之间的相乘
{
BigNum ret;
int i,j,up;
int temp,temp1;
for(i=;i<len;i++)
{
up=;
for(j=;j<T.len;j++)
{
temp=a[i]*T.a[j]+ret.a[i+j]+up;
if(temp>MAXN)
{
temp1=temp-temp/(MAXN+)*(MAXN+);
up=temp/(MAXN+);
ret.a[i+j]=temp1;
}
else
{
up=;
ret.a[i+j]=temp;
}
}
if(up!=)
ret.a[i+j]=up;
}
ret.len=i+j;
while(ret.a[ret.len-]== && ret.len>)
ret.len--;
return ret;
}
BigNum BigNum::operator/(const int &b)const //大数对一个整数进行相除运算
{
BigNum ret;
int i,down=;
for(i=len-;i>=;i--)
{
ret.a[i]=(a[i]+down*(MAXN+))/b;
down=a[i]+down*(MAXN+)-ret.a[i]*b;
}
ret.len=len;
while(ret.a[ret.len-]== && ret.len>)
ret.len--;
return ret;
}
int BigNum::operator%(const int &b)const //大数对一个 int类型的变量进行取模
{
int i,d=;
for(i=len-;i>=;i--)
d=((d*(MAXN+))%b+a[i])%b;
return d;
}
BigNum BigNum::operator^(const int &n)const //大数的n次方运算
{
BigNum t,ret();
int i;
if(n<)exit(-);
if(n==)return ;
if(n==)return *this;
int m=n;
while(m>)
{
t=*this;
for(i=;(i<<)<=m;i<<=)
t=t*t;
m-=i;
ret=ret*t;
if(m==)
ret=ret*(*this);
}
return ret;
}
bool BigNum::operator>(const BigNum &T)const //大数和另一个大数的大小比较
{
int ln;
if(len>T.len)
return true;
else if(len==T.len)
{
ln=len-;
while(a[ln]==T.a[ln]&&ln>=)
ln--;
if(ln>= && a[ln]>T.a[ln])
return true;
else
return false;
}
else
return false;
}
bool BigNum::operator>(const int &t)const //大数和一个int类型的变量的大小比较
{
BigNum b(t);
return *this>b;
}
void BigNum::print() //输出大数
{
int i;
printf("%d",a[len-]);
for(i=len-;i>=;i--)
printf("%04d",a[i]);
printf("\n");
} BigNum f[];//卡特兰数
int main()
{
f[]=;
for(int i=;i<=;i++)
f[i]=f[i-]*(*i-)/(i+);//卡特兰数递推式
int n;
while(scanf("%d",&n)==)
{
if(n==-)
break;
f[n].print();
}
return ;
}
最新文章
- asp.net core 负载均衡集群搭建(centos7+nginx+supervisor+kestrel)
- jQuery—常用操作
- c/c++中关于sizeof、strlen的使用说明
- js 判断IE浏览器,包含IE6/7/8/9
- 用Linq操作数据小记
- IIS7 IIS7.5 IIS8.5 HTTP 错误 500.19 – Internal Server Error解决方案小记
- 三元组表压缩存储稀疏矩阵实现稀疏矩阵的快速转置(Java语言描述)
- (转)SQL按照日、周、月、年统计数据
- iOS里面如何同时使用开启ARC的库 和 没有开启 ARC的库,ARC 与非 ARC同时存在的问题
- cas+tomcat+shiro实现单点登录-2-部署cas server到tomcat
- onPostCreate——Activity彻底运行起来之后的回调
- 【基础】EM 还是 REM?这是一个问题!
- gnocchi resource批量删除
- OpenGL 太阳系行星拾取例子(GL_SELECT) VS2008 + glut实现
- AngularJs ng-change事件/指令(转)
- 高通平台framework,hal,kernel打开log【转】
- 每个Android开发者必须知道的内存管理知识
- Mysql中FIND_IN_SET和REPLACE函数简介
- bzoj 3144 [Hnoi2013]切糕——最小割
- w.5 Y k J.COm 9 如何做好总经理助理