POJ 2084 Game of Connections

Game of Connections

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 4839		Accepted: 2515

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
3
-1

Sample Output

2
5

Source

Shanghai 2004 Preliminary

/*
卡特兰数 + 大数运算，一开始自己推公式得到的结论是:
f(2 * n) = f(0) * f(2 * n - 2) + f(2) * f(2 * n - 4) + f(4) * f(2 * n - 6) + ... + f(2 * n - 2) * f(0);
然后纯粹基于递推来算, 发现结果是对的，但是速度太慢，超时了。后来想了想，这不就是卡特兰数吗？呵呵，问题解决了
F(n) = F(0) * F(n - 1) + F(1) * F(n - 2) + ... + F(n - 1) * F(0) = C(2 * n, n) / (n + 1), F(0) = 1
代码很长，大部分是自己写的大数运算工具模板, 哈哈
*/

#include <iostream>
#include <string>
#define BIGINTEGER_LEN_TYPE int
#define MAX_N 201
using namespace std;

string num[MAX_N];
string cval[MAX_N][MAX_N];

//大数加法
string bigIntegerAdd(const string left, const string right)
{
    BIGINTEGER_LEN_TYPE lenl = static_cast<BIGINTEGER_LEN_TYPE>(left.size());
    BIGINTEGER_LEN_TYPE lenr = static_cast<BIGINTEGER_LEN_TYPE>(right.size());
    std::string res = "";
    
    //get the minimum length of the two string
    BIGINTEGER_LEN_TYPE minLen = (lenl <= lenr) ? lenl : lenr;
    BIGINTEGER_LEN_TYPE maxLen = (lenl <= lenr) ? lenr : lenl;
    std::string longerStr = (lenl <= lenr) ? right : left;
    
    int residue = 0, sum = 0, quotient = 0;
    //add operation, first part
    BIGINTEGER_LEN_TYPE pos1;
    for(pos1 = 0; pos1 <= minLen - 1; pos1++)
    {
        sum = (left[pos1] - '0') + (right[pos1] - '0') + quotient;
        quotient = sum / 10;
        residue = sum % 10;
        res += residue + '0';
    }
    //add operation, second part
    for(BIGINTEGER_LEN_TYPE pos2 = pos1; pos2 <= maxLen - 1; pos2 ++)
    {
        sum = (longerStr[pos2] - '0') + quotient;
        quotient = sum / 10;
        residue = sum % 10;
        res += residue + '0';
    }
    //add the extra carry
    while(quotient != 0)
    {
        residue = quotient % 10;
        quotient = quotient / 10;
        res += residue + '0';
    }
    //std::cout<<"res size:"<<res.length()<<std::endl;
    return res;
}

//大数乘法
string bigIntegerMult(const string left, const string right)
{
    BIGINTEGER_LEN_TYPE minLen = static_cast<BIGINTEGER_LEN_TYPE>(left.length());
    BIGINTEGER_LEN_TYPE maxLen = static_cast<BIGINTEGER_LEN_TYPE>(right.length());
    std::string longerStr = "";
    std::string shorterStr = "";
    std::string res = "";
    //get the longer and short strings and corresponded length
    if(left.length() <= right.length())
    {
        minLen = static_cast<BIGINTEGER_LEN_TYPE>(left.length());
        maxLen = static_cast<BIGINTEGER_LEN_TYPE>(right.length());
        shorterStr = left;
        longerStr = right;
    }
    else
    {
        minLen = static_cast<BIGINTEGER_LEN_TYPE>(right.length());
        maxLen = static_cast<BIGINTEGER_LEN_TYPE>(left.length());
        shorterStr = right;
        longerStr = left;
    }
    BIGINTEGER_LEN_TYPE pos1 = 0;
    BIGINTEGER_LEN_TYPE pos2 = 0;
    //start from the first digit of the shorter string
    for(pos1 = 0; pos1 <= minLen - 1; pos1++)
    {
        //multiply each digit of the longer string
        int residue = 0, product = 0, quotient = 0;
        BIGINTEGER_LEN_TYPE curPos = 0;
        for(pos2 = 0; pos2 <= maxLen - 1; pos2++)
        {
            curPos = pos1 + pos2;
            //new space
            if(res.length() == 0 || curPos > int(res.length() - 1))
            {
                product = (shorterStr[pos1] - '0') * (longerStr[pos2] - '0') + quotient;
                quotient = product / 10;
                residue = product % 10;
                res += residue + '0';
            }
            //space already exists, just add the original value to product
            else
            {
                product = (shorterStr[pos1] - '0') * (longerStr[pos2] - '0') + quotient + (res[curPos] - '0');
                quotient = product / 10;
                residue = product % 10;
                res[curPos] = residue + '0'; 
            }
        }
        //process the extra quotient
        //start position
        curPos = maxLen + pos1;
        while(quotient != 0)
        {
            if(res.length() == 0 || curPos > int(res.length() - 1))
            {
                residue = quotient % 10;
                quotient = quotient / 10;
                res += residue + '0';
            }
            else
            {
                quotient = quotient + (res[curPos] - '0');
                residue = quotient % 10;
                quotient = quotient / 10;
                res[curPos] = residue + '0';
            }
            curPos++;
        }
    }
    //std::cout<<res.length()<<std::endl;
    return res;
    
}

//对字符串str进行翻转
string getReverse(const string str)
{
    std::string revStr = "";
    BIGINTEGER_LEN_TYPE pos = static_cast<BIGINTEGER_LEN_TYPE>(str.length()) - 1;
    for(; pos >= 0; pos--)
        revStr += str[pos];
    return revStr;
}

//比较两个大数的大小
int bigIntegerCmp(const string left, const string right)
{
    BIGINTEGER_LEN_TYPE lenl = static_cast<BIGINTEGER_LEN_TYPE>(left.length());
    BIGINTEGER_LEN_TYPE lenr = static_cast<BIGINTEGER_LEN_TYPE>(right.length());
    if(lenl < lenr)
        return -1;
    else if(lenl > lenr)
        return 1;
    return strcmp(getReverse(left).c_str(), getReverse(right).c_str());
}

//大数减法
string bigIntegerSub(const string left, const string right)
{
    std::string biggerStr = "";
    std::string smallerStr = "";
    std::string res = "";
    BIGINTEGER_LEN_TYPE minLen = 0;
    BIGINTEGER_LEN_TYPE maxLen = 0;
    
    //get the bigger integer and smaller integer
    int cmpRes = bigIntegerCmp(left, right);
    if(cmpRes == -1 || cmpRes == 0)
    {
        smallerStr = left;
        biggerStr = right;
    }
    else
    {
        smallerStr = right;
        biggerStr = left;
    }
    //get related size
    minLen = static_cast<BIGINTEGER_LEN_TYPE>(smallerStr.length());
    maxLen = static_cast<BIGINTEGER_LEN_TYPE>(biggerStr.length());
    
    int extra = 0, temp = 0, subRes = 0;
    //subtraction operation, first part
    BIGINTEGER_LEN_TYPE pos1;
    for(pos1 = 0; pos1 <= minLen - 1; pos1++)
    {
        int curL = biggerStr[pos1] - '0';
        int curR = smallerStr[pos1] - '0';
        temp = 0;
        while((subRes = (curL - curR + 10 * temp - extra)) < 0)
            temp++;
        res += subRes + '0';
        extra = temp;
    }
    //subtraction operation, second part
    for(BIGINTEGER_LEN_TYPE pos2 = pos1; pos2 <= maxLen - 1; pos2 ++)
    {
        int curL = biggerStr[pos2] - '0';
        temp = 0;
        while((subRes = (curL + 10 * temp - extra)) < 0)
            temp++;
        res += subRes + '0';
        extra = temp;
    }
    //remove the zero at head
    while(res[res.length() - 1] == '0' && res.length() >= 2)
        res = res.substr(0, res.length() - 1);
    
    //std::cout<<"res size:"<<res.length()<<std::endl;
    return res;
}

//把整数转换为字符串
string getStr(int a)
{
    string res = "";
    if(a == 0) return "0";
    else
    {
        while(a)
        {
            res = char(a % 10 + '0') + res;
            a = a / 10;
        }
    }
    return res;
}

//大数除法
void bigIntegerDiv(const std::string left, const std::string right, std::string & quotient, std::string & residual)
{
    int type = bigIntegerCmp(left, right);
    //left < right
    if(type == -1)
    {
        quotient = "0";
        residual = left;
        return;
    }
    //left = right
    else if(type == 0)
    {
        quotient = "1";
        residual = "0";
        return;
    }
    //left > right
    //initialize the related data 
    quotient = "";
    residual = "";
    std::string dividend = left;
    std::string divisor = right; 
    BIGINTEGER_LEN_TYPE lenDend = static_cast<BIGINTEGER_LEN_TYPE>(left.length());
    BIGINTEGER_LEN_TYPE lenDsor = static_cast<BIGINTEGER_LEN_TYPE>(right.length());
    
    std::string temp = "";
    std::string curStr = "";
    std::string tryStr = "";
    BIGINTEGER_LEN_TYPE curPos = 0;
    int choice = 0;
    bool visitedFirst = false;
    //start from the head of the dividend
    for(curPos = lenDend - 1; curPos >= 0; curPos--)
    {
        curStr = dividend[curPos] + curStr;
        //curStr > divisor, can be processed
        if(bigIntegerCmp(curStr, divisor) >= 0)
        {
            //try the quotient from 1 to 10 until the result of choice * divisor is the biggest less than curStr
            for(choice = 1; choice <= 10; choice++)
            {
                temp = "";
                temp += char(choice + '0');
                tryStr = bigIntegerMult(divisor, temp);
                if(bigIntegerCmp(tryStr, curStr) > 0)
                {
                    choice--;
                    break;
                }
            }
            //right now, choice is just the current quotient and should be appended ahead to quotient
            quotient = char(choice + '0') + quotient;
            temp = "";
            temp += char(choice + '0');
            //update curStr
            curStr = bigIntegerSub(curStr, bigIntegerMult(divisor, temp));
            if(curPos == 0)
                residual = curStr;
            //set visitedFirst, visitedFirst is used to prevent producing '0' quotient
            visitedFirst = true;
        }
        //curStr is not enough to be divided by divisor, so the current quotient is '0' and should be appended to 'quotient'
        else if(visitedFirst)
            quotient = '0' + quotient;
        if(curPos == 0)
        {
            residual = curStr;
            break;
        }
        if(curStr == "0")
            curStr = "";
    }
    residual = curStr;
    return;
}

string getCval(int p, int q)
{
    if(p == q || q == 0) return "1";
    if(q == 1) return getReverse(getStr(p));
    
    if(cval[p][q] != "0") return cval[p][q];
    
    return cval[p][q] = bigIntegerAdd(getCval(p - 1, q - 1), getCval(p - 1, q));
} 

//计算k的卡特兰数，下标从0开始
string solve1(int k)
{
    if(num[k] != "0") return num[k];
    string quotient, residual;

    bigIntegerDiv(getCval(2 * k, k), getReverse(getStr(k + 1)), quotient, residual);
    
    return quotient;
}

int main()
{
    int i, j, p;
    for(i = 1; i < MAX_N; i++) 
    {
        num[i] = "0";
        for(j = 1; j < MAX_N; j++)
            cval[i][j] = "0"; 
    }
    num[1] = "1";
    while(scanf("%I64d", &p) && p != -1)
        cout<<getReverse(solve1(p))<<endl;
    return 0;
}