hdu 1023 Train Problem II
2024-10-16 16:09:06
题目连接
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 ;
}
最新文章
- sqlserver 游标的使用
- Retrofit源码分析(一)
- .Net下的 ORM框架介紹
- Bise IE6 在你的网站上加上它让IE滚蛋吧
- sublime和python
- (C语言)精髓——指针
- Win7下打开计算机管理时出现错误的解决办法
- 最长递增子序列 O(NlogN)算法
- Kafka可靠性的思考
- HDU 4483 Lattice triangle(欧拉函数)
- 今天升级了ADT到ADT 22.6.1,打包混淆的时候就出现了问题
- Python3 如何优雅地使用正则表达式(详解一)
- javascript正则表达式小数类型
- hdu 5635 LCP Array(BC第一题)
- [Python Study Notes] Python的安装
- CentOS7.2安装jdk7u80
- 深入理解JS函数中this指针的指向
- [转帖]git、github、gitlab之间的关系
- 题解——loj6281 数列分块入门5 (分块)
- IE下的Firebug——IE WebDeveloper js debug
热门文章
- 解决ScrollView下嵌套ListView、GridView显示不全的问题
- Asp.Net获取IP的方法
- Visual C++ 开发心得与调试技巧
- CSS实用的代码段
- HTML5-新API-geolocation-实例-距离跟踪器
- Web发布 未能加载文件或程序集“”或它的某一个依赖项。系统找不到指定的...
- undefined reference to `pthread_create&#39;问题解决
- THINKPHP 清除HTML注释、换行符、空格、制表符等
- IIS报错 未将对象引用设置到对象的实例。
- sql查看当前周数