hdu1023

maksyuki 发表于 oj 分类，标签: 组合数学-Catalan数

15 9月 2015

Train Problem II

Problem 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.

Sample Input

Sample Output

16796

Hint The result will be very large, so you may not process it by 32-bit integers.

Author

Ignatius.L

题目类型：高精度Catalan数

算法分析：直接使用高精度Catalan数计算即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 10000 + 7;

const int maxn = 10000 + 66;

string Mul (string a, long long b)//高精度a乘单精度b
{
    string ans;
    long long na[maxn], La = a.size ();// maxn表示相乘结果的最大可能位数

    fill (na, na + maxn, 0);

    for (long long i = La - 1; i >= 0; i--)
        na[La-i-1] = a[i] - '0';

    long long w = 0;

    for (long long i = 0; i < La; i++)
    {
        na[i] = na[i] * b + w;
        w = na[i] / 10;
        na[i] = na[i] % 10;
    }

    while (w)
    {
        na[La++] = w % 10;
        w /= 10;
    }

    La--;

    while (La >= 0) ans += na[La--] + '0';

return ans;
}

string Div (string a, long long b)//高精度a除以单精度b
{
    string r;
    long long d = 0;

    if(a == "0")
        return a;//特判

    for (long long i = 0; i < a.size (); i++)
    {
        r += (d * 10 + a[i] - '0') / b + '0';//求出商
        d = (d * 10 + (a[i] - '0')) % b;//求出余数
    }

    long long p = 0;
    for (long long i = 0; i < r.size (); i++)
        if (r[i] != '0')
        {
            p = i;
            break;
        }

return r.substr (p);
}

string Catalan (long long val)
{
    string a("1");
    for (long long i = 1; i <= val; i++)
    {
        a = Mul (a, (4 * i - 2));
        a = Div (a, (i + 1));
    }

return a;
}

int main()
{
//    ifstream cin ("aaa.txt");

    long long n;
    while (cin >> n)
    {
        cout << Catalan (n) << endl;
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 10000 + 7;

const int maxn = 10000 + 66;

string Mul (string a, long long b)//高精度a乘单精度b

{

string ans;

long long na[maxn], La = a.size ();// maxn表示相乘结果的最大可能位数

fill (na, na + maxn, 0);

for (long long i = La - 1; i >= 0; i--)

na[La-i-1] = a[i] - '0';

long long w = 0;

for (long long i = 0; i < La; i++)

{

na[i] = na[i] * b + w;

w = na[i] / 10;

na[i] = na[i] % 10;

}

while (w)

{

na[La++] = w % 10;

w /= 10;

}

La--;

while (La >= 0) ans += na[La--] + '0';

return ans;

}

string Div (string a, long long b)//高精度a除以单精度b

{

string r;

long long d = 0;

if(a == "0")

return a;//特判

for (long long i = 0; i < a.size (); i++)

{

r += (d * 10 + a[i] - '0') / b + '0';//求出商

d = (d * 10 + (a[i] - '0')) % b;//求出余数

}

long long p = 0;

for (long long i = 0; i < r.size (); i++)

if (r[i] != '0')

{

p = i;

break;

}

return r.substr (p);

}

string Catalan (long long val)

{

string a("1");

for (long long i = 1; i <= val; i++)

{

a = Mul (a, (4 * i - 2));

a = Div (a, (i + 1));

}

return a;

}

int main()

{

// ifstream cin ("aaa.txt");

long long n;

while (cin >> n)

{

cout << Catalan (n) << endl;

}

return 0;

}

hdu1009

hdu1025

超客的水墨烟雨

hdu1023

Train Problem II

分类目录

标签云

书签

近期评论

2024年12月
一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31