首页 > 代码库 > BZOJ 2822 AHOI 2012 树屋阶梯 卡特兰数+高精度

BZOJ 2822 AHOI 2012 树屋阶梯 卡特兰数+高精度

题目大意:高精度卡特兰数。


思路:上维基上看看,有一个模型和这个题一模一样,然后就剩下水水的高精度了。

(谁来教教我java...


CODE:


#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define BASE 10000
#define MAX 100010
using namespace std;
 
struct BigInt{
    int num[MAX],len;
     
    BigInt(int _ = 0) {
        num[len = 1] = _;
    }
    BigInt operator +(const BigInt &a)const {
        BigInt re;
        re.len = max(len,a.len);
        int temp = 0;
        for(int i = 1; i <= a.len; ++i) {
            re.num[i] = temp + num[i] + a.num[i];
            temp = re.num[i] / BASE;
            re.num[i] %= BASE;
        }
        if(temp)    re.num[++re.len] = temp;
        return re;
    }
    BigInt operator *(int a)const {
        BigInt re;
        re.len = len;
        int temp = 0;
        for(int i = 1; i <= len; ++i) {
            re.num[i] = temp + num[i] * a;
            temp = re.num[i] / BASE;
            re.num[i] %= BASE;
        }
        while(temp) re.num[++re.len] = temp % BASE,temp /= BASE;
        return re;
    }
    BigInt operator /(int a)const {
        BigInt re;
        re.len = len;
        int temp = 0;
        for(int i = len; i; --i) {
            re.num[i] = (temp + num[i]) / a;
            temp = (temp + num[i]) % a * BASE;
        }
        while(!re.num[re.len])  --re.len;
        return re;
    }
};
 
int main()
{
    int x;
    cin >> x;
    BigInt ans(1);
    for(int i = 2; i <= x; ++i)
        ans = ans * (4 * i - 2) / (i + 1);
    printf("%d",ans.num[ans.len]);
    for(int i = ans.len - 1; i; --i)
        printf("%04d",ans.num[i]);
    return 0;
}


BZOJ 2822 AHOI 2012 树屋阶梯 卡特兰数+高精度