0; //空集
i<<i; //只含第i的元素的集合{i}
(1<<n)-1;//含有全部i个元素的集合{0,1,2,3,...,n-1}
if(S>>i & 1); //判断第i个元素是否属于集合sp
S|1<<i;//向集合S中加入第i个元素
S&~(1<<i);//从集合S中去除第i个元素
S|T;//集合S与集合T的并
S&T;//集合S与集合T的交
for(int i = 0 ; i < 1 << n ; i++) //枚举集合{0,1,2,3,...,n-1}的全部子集
{
;//对子集的处理
}
//m[0,1,2,3....,n-1] 输入的原始序列
//dp[i]表示长度为i的子序列的最后一个元素的最大值
memset(dp,0,sizeof(dp));
for(int i = 0; i < n ; i++)
{
*std::upper_bound(dp+1,dp+1+n,m[i],std::greater<int>()) = m[i];
}
int ret = 1;
while(dp[ret] != 0)
{
ret++;
}
ret = ret -1;
//l[0,1,2,3....,n-1] 输入的原始序列
//dp[i]表示长度为i的子序列的最后一个元素可以允许的最小值
for(int i = 0 ; i <= idx ; i++)
dp[i] = INT_MAX;
for(int i = 0 ; i < idx ; i++)
{
*lower_bound(dp + 1, dp + idx, l[i]) = l[i];
}
int ret = 1;
while(dp[ret]!=INT_MAX)
ret++;
ret = ret - 1;int ret = 1;
for(int i = 0 ; i < idx ; i++)
{
for(int j = 1 ; j <= ret ; j++)
{
if(p[i].y >= dp[j])
{
dp[j] = p[i].y;
break;
}
}
if(dp[ret] != 0 ) ret = ret + 1;
}
ret = ret -1;int ret = 1;
for(int i = 0 ; i < m ; i++)
{
for(int j = 1; j <= ret ; j++ )
{
if( dp[j] < dolls[i].h )
{
dp[j] = dolls[i].h;
break;
}
}
if(dp[ret] != 0 ) ret ++;
}
ret = ret -1;// b不能是負數
int pow(int a, int b) // aᵇ
{
int x = 1;
while(b>0)
{
if (b & 1)
x =x * a;
a = a * a;
b = b / 2;
}
return x;
}
// b不能是負數
uint32_t pow_mod(uint32_t a,uint32_t b ,uint32_t m) // aᵇ mod m
{
int32_t x = 1;
a = a % m;
while(b>0)
{
if (b & 1)
x =(x * a) % m;
a = (a * a) %m;
b = b / 2;
}
return x;
}//HDU 1134 求卡特兰数
#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
using std::istream;
using std::ostream;
class BigNum
{
private:
int a[500]; //可以控制大数的位数
int len;
public:
BigNum(){len = 1;memset(a, 0, 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 = 0;
memset(a, 0, sizeof(a));
while (d > MAXN)
{
c = d - (d / (MAXN + 1)) * (MAXN + 1);
d = d / (MAXN + 1);
a[len++] = c;
}
a[len++] = d;
}
BigNum::BigNum(const char *s) //将一个字符串类型的变量转化为大数
{
int t, k, index, L, i;
memset(a, 0, sizeof(a));
L = strlen(s);
len = L / DLEN;
if (L % DLEN)
len++;
index = 0;
for (i = L - 1; i >= 0; i -= DLEN)
{
t = 0;
k = i - DLEN + 1;
if (k < 0)
k = 0;
for (int j = k; j <= i; j++)
t = t * 10 + s[j] - '0';
a[index++] = t;
}
}
BigNum::BigNum(const BigNum &T) : len(T.len) //拷贝构造函数
{
int i;
memset(a, 0, sizeof(a));
for (i = 0; i < len; i++)
a[i] = T.a[i];
}
BigNum &BigNum::operator=(const BigNum &n) //重载赋值运算符，大数之间赋值运算
{
int i;
len = n.len;
memset(a, 0, sizeof(a));
for (i = 0; i < len; i++)
a[i] = n.a[i];
return *this;
}
istream &operator>>(istream &in, BigNum &b)
{
char ch[MAXSIZE * 4];
int i = -1;
in >> ch;
int L = strlen(ch);
int count = 0, sum = 0;
for (i = L - 1; i >= 0;)
{
sum = 0;
int t = 1;
for (int j = 0; j < 4 && i >= 0; j++, i--, t *= 10)
{
sum += (ch[i] - '0') * t;
}
b.a[count] = sum;
count++;
}
b.len = count++;
return in;
}
ostream &operator<<(ostream &out, BigNum &b) //重载输出运算符
{
int i;
cout << b.a[b.len - 1];
for (i = b.len - 2; i >= 0; 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 = 0; i < big; i++)
{
t.a[i] += T.a[i];
if (t.a[i] > MAXN)
{
t.a[i + 1]++;
t.a[i] -= MAXN + 1;
}
}
if (t.a[big] != 0)
t.len = big + 1;
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 = 0;
}
else
{
t1 = T;
t2 = *this;
flag = 1;
}
big = t1.len;
for (i = 0; i < big; i++)
{
if (t1.a[i] < t2.a[i])
{
j = i + 1;
while (t1.a[j] == 0)
j++;
t1.a[j--]--;
while (j > i)
t1.a[j--] += MAXN;
t1.a[i] += MAXN + 1 - t2.a[i];
}
else
t1.a[i] -= t2.a[i];
}
t1.len = big;
while (t1.a[len - 1] == 0 && t1.len > 1)
{
t1.len--;
big--;
}
if (flag)
t1.a[big - 1] = 0 - t1.a[big - 1];
return t1;
}
BigNum BigNum::operator*(const BigNum &T) const //两个大数之间的相乘
{
BigNum ret;
int i, j, up;
int temp, temp1;
for (i = 0; i < len; i++)
{
up = 0;
for (j = 0; j < T.len; j++)
{
temp = a[i] * T.a[j] + ret.a[i + j] + up;
if (temp > MAXN)
{
temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
up = temp / (MAXN + 1);
ret.a[i + j] = temp1;
}
else
{
up = 0;
ret.a[i + j] = temp;
}
}
if (up != 0)
ret.a[i + j] = up;
}
ret.len = i + j;
while (ret.a[ret.len - 1] == 0 && ret.len > 1)
ret.len--;
return ret;
}
BigNum BigNum::operator/(const int &b) const //大数对一个整数进行相除运算
{
BigNum ret;
int i, down = 0;
for (i = len - 1; i >= 0; i--)
{
ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
}
ret.len = len;
while (ret.a[ret.len - 1] == 0 && ret.len > 1)
ret.len--;
return ret;
}
int BigNum::operator%(const int &b) const //大数对一个 int类型的变量进行取模
{
int i, d = 0;
for (i = len - 1; i >= 0; i--)
d = ((d * (MAXN + 1)) % b + a[i]) % b;
return d;
}
BigNum BigNum::operator^(const int &n) const //大数的n次方运算
{
BigNum t, ret(1);
int i;
if (n < 0)
exit(-1);
if (n == 0)
return 1;
if (n == 1)
return *this;
int m = n;
while (m > 1)
{
t = *this;
for (i = 1; (i << 1) <= m; i <<= 1)
t = t * t;
m -= i;
ret = ret * t;
if (m == 1)
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 - 1;
while (a[ln] == T.a[ln] && ln >= 0)
ln--;
if (ln >= 0 && 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 - 1]);
for (i = len - 2; i >= 0; i--)
printf("%04d", a[i]);
printf("\n");
}
BigNum f[110]; //卡特兰数
int main()
{
f[0] = 1;
for (int i = 1; i <= 100; i++)
f[i] = f[i - 1] * (4 * i - 2) / (i + 1); //卡特兰数递推式
int n;
while (scanf("%d", &n) == 1)
{
if (n == -1)
break;
f[n].print();
}
return 0;
}struct Trie
{
int ch[maxnod][sigma_size];
int val[maxnod];// 附加信息
int prefix[maxnod];//记录前缀数目
int sz;//
Trie(){sz = 1;memset(ch[0],0,sizeof(ch[0]));};
int idx(char c) {return c - 'A';}
//插入字符串s，附加信息v。
int insert(char* s,int v)
{
int u = 0, n = strlen(s);
for(int i = 0; i < n ; i++)
{
int c = idx(s[i]);
if(!ch[u][c])
{
memset(ch[sz],0,sizeof(ch[sz]));
val[sz] = 0;// 0表示中间结点
prefix[sz] = 0;
ch[u][c] = sz++;
}
u = ch[u][c];
prefix[u]++;
}
val[u] = v;
}
int find(char* s)
{
int u = 0,n = strlen(s);
for(int i = 0; i < n ; i++)
{
int c = idx(s[i]);
if(!ch[u][c]) return 0 ;
u = ch[u][c];
}
if(val[u]==0) return 0;
else return 1;
}
};