题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=1212

Train Problem II

Description

As we all know the Train Problem I, the boss of the Ignatius Train Station want to know if all the trains come in strict-increasing order, how many orders that all the trains can get out of the railway.

Input

The input contains several test cases. Each test cases consists of a number N(1<=N<=100). The input is terminated by the end of file.

Output

For each test case, you should output how many ways that all the trains can get out of the railway.

SampleInput

1
2
3
10

SampleOutput

1
2
5
16796

卡特兰数。。

$ f(n) = f(n-1)*(n*4-2)/(n-1)$

 #include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<cstdio>
#include<vector>
#include<string>
#include<map>
#include<set>
using std::cin;
using std::max;
using std::cout;
using std::endl;
using std::string;
using std::istream;
using std::ostream;
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define iter(c) decltype((c).begin())
#define cls(arr,val) memset(arr,val,sizeof(arr))
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, j, n) for (int i = j; i < (int)(n); i++)
#define fork(i, k, n) for (int i = (int)k; i <= (int)n; i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
struct BigN {
typedef unsigned long long ull;
static const int Max_N = ;
int len, data[Max_N];
BigN() { memset(data, , sizeof(data)), len = ; }
BigN(const int num) {
memset(data, , sizeof(data));
*this = num;
}
BigN(const char *num) {
memset(data, , sizeof(data));
*this = num;
}
void clear() { len = , memset(data, , sizeof(data)); }
BigN& clean(){ while (len > && !data[len - ]) len--; return *this; }
string str() const {
string res = "";
for (int i = len - ; ~i; i--) res += (char)(data[i] + '');
if (res == "") res = "";
res.reserve();
return res;
}
BigN operator = (const int num) {
int j = , i = num;
do data[j++] = i % ; while (i /= );
len = j;
return *this;
}
BigN operator = (const char *num) {
len = strlen(num);
for (int i = ; i < len; i++) data[i] = num[len - i - ] - '';
return *this;
}
BigN operator + (const BigN &x) const {
BigN res;
int n = max(len, x.len) + ;
for (int i = , g = ; i < n; i++) {
int c = data[i] + x.data[i] + g;
res.data[res.len++] = c % ;
g = c / ;
}
return res.clean();
}
BigN operator * (const BigN &x) const {
BigN res;
int n = x.len;
res.len = n + len;
for (int i = ; i < len; i++) {
for (int j = , g = ; j < n; j++) {
res.data[i + j] += data[i] * x.data[j];
}
}
for (int i = ; i < res.len - ; i++) {
res.data[i + ] += res.data[i] / ;
res.data[i] %= ;
}
return res.clean();
}
BigN operator * (const int num) const {
BigN res;
res.len = len + ;
for (int i = , g = ; i < len; i++) res.data[i] *= num;
for (int i = ; i < res.len - ; i++) {
res.data[i + ] += res.data[i] / ;
res.data[i] %= ;
}
return res.clean();
}
BigN operator - (const BigN &x) const {
assert(x <= *this);
BigN res;
for (int i = , g = ; i < len; i++) {
int c = data[i] - g;
if (i < x.len) c -= x.data[i];
if (c >= ) g = ;
else g = , c += ;
res.data[res.len++] = c;
}
return res.clean();
}
BigN operator / (const BigN &x) const {
BigN res, f = ;
for (int i = len - ; ~i; i--) {
f *= ;
f.data[] = data[i];
while (f >= x) {
f -= x;
res.data[i]++;
}
}
res.len = len;
return res.clean();
}
BigN operator % (const BigN &x) {
BigN res = *this / x;
res = *this - res * x;
return res;
}
BigN operator += (const BigN &x) { return *this = *this + x; }
BigN operator *= (const BigN &x) { return *this = *this * x; }
BigN operator -= (const BigN &x) { return *this = *this - x; }
BigN operator /= (const BigN &x) { return *this = *this / x; }
BigN operator %= (const BigN &x) { return *this = *this % x; }
bool operator < (const BigN &x) const {
if (len != x.len) return len < x.len;
for (int i = len - ; ~i; i--) {
if (data[i] != x.data[i]) return data[i] < x.data[i];
}
return false;
}
bool operator >(const BigN &x) const { return x < *this; }
bool operator<=(const BigN &x) const { return !(x < *this); }
bool operator>=(const BigN &x) const { return !(*this < x); }
bool operator!=(const BigN &x) const { return x < *this || *this < x; }
bool operator==(const BigN &x) const { return !(x < *this) && !(x > *this); }
friend istream& operator >> (istream &in, BigN &x) {
string src;
in >> src;
x = src.c_str();
return in;
}
friend ostream& operator << (ostream &out, const BigN &x) {
out << x.str();
return out;
}
}A[], B;
inline void init() {
A[] = ;
rep(i, , ) {
B = * i - ;
A[i] = A[i - ] * B / (i + );
B.clear();
}
}
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w+", stdout);
#endif
init();
std::ios::sync_with_stdio(false);
int n;
while (cin >> n) cout << A[n] << endl;
return ;
}

最新文章

  1. sqlserver 游标的使用
  2. Retrofit源码分析(一)
  3. .Net下的 ORM框架介紹
  4. Bise IE6 在你的网站上加上它让IE滚蛋吧
  5. sublime和python
  6. (C语言)精髓——指针
  7. Win7下打开计算机管理时出现错误的解决办法
  8. 最长递增子序列 O(NlogN)算法
  9. Kafka可靠性的思考
  10. HDU 4483 Lattice triangle(欧拉函数)
  11. 今天升级了ADT到ADT 22.6.1,打包混淆的时候就出现了问题
  12. Python3 如何优雅地使用正则表达式(详解一)
  13. javascript正则表达式小数类型
  14. hdu 5635 LCP Array(BC第一题)
  15. [Python Study Notes] Python的安装
  16. CentOS7.2安装jdk7u80
  17. 深入理解JS函数中this指针的指向
  18. [转帖]git、github、gitlab之间的关系
  19. 题解——loj6281 数列分块入门5 (分块)
  20. IE下的Firebug——IE WebDeveloper js debug

热门文章

  1. 解决ScrollView下嵌套ListView、GridView显示不全的问题
  2. Asp.Net获取IP的方法
  3. Visual C++ 开发心得与调试技巧
  4. CSS实用的代码段
  5. HTML5-新API-geolocation-实例-距离跟踪器
  6. Web发布 未能加载文件或程序集“”或它的某一个依赖项。系统找不到指定的...
  7. undefined reference to `pthread_create&#39;问题解决
  8. THINKPHP 清除HTML注释、换行符、空格、制表符等
  9. IIS报错 未将对象引用设置到对象的实例。
  10. sql查看当前周数