树屋阶梯

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1997 字
用若干块木材搭高度为N的树屋阶梯，求搭建方法
一本通
练习
正文

/*
原题：T1662「一本通 6.6 练习 11」树屋阶梯
题意：用若干块木材搭高度为 N 的树屋阶梯，求搭建方法数（数值可能很大）。
思路：搭 N 级阶梯的方法数就是第 N 个 Catalan 数 C_N = C(2N,N)/(N+1)。
用高精度先按递推 res=res·(n-r+i)/i 算出 C(2N,N)，再除以 (N+1) 即得。
复杂度：时间 O(N·精度位数)，空间 O(精度位数)
易错点：1) 结果远超 64 位整数，必须用高精度保存并输出；
2) 除以 (N+1) 要在算出组合数之后整体做一次，不能穿插在递推里；
3) 输出中间段要按 4 位补前导零。
*/
#include <bits/stdc++.h>
using namespace std;
const int BASE=10000;
struct Big{
    vector<int> d;
    Big(long long v=0){
        if(v==0){
            d.push_back(0);
        }else{
            while(v>0){
                d.push_back(v%BASE);
                v/=BASE;
            }
        }
    }
    void trim(){
        while(d.size()>1 && d.back()==0){
            d.pop_back();
        }
    }
};
Big mulSmall(const Big& x,long long m){
    Big r;
    size_t n=x.d.size()+40;
    vector<long long> tmp(n,0);
    for(size_t i=0;i<x.d.size();i++){
        long long cur=(long long)x.d[i]*m;
        size_t j=i;
        while(cur>0 && j<n){
            tmp[j]+=cur%BASE;
            cur/=BASE;
            j++;
        }
    }
    r.d.assign(n+2,0);
    long long carry=0;
    for(size_t i=0;i<n+2;i++){
        long long cur=(i<n?tmp[i]:0)+carry;
        r.d[i]=cur%BASE;
        carry=cur/BASE;
    }
    while(carry>0){
        r.d.push_back(carry%BASE);
        carry/=BASE;
    }
    r.trim();
    return r;
}
Big divSmall(const Big& x,long long m){
    Big r;
    r.d.assign(x.d.size(),0);
    long long rem=0;
    for(size_t i=x.d.size();i-- >0;){
        long long cur=rem*BASE+x.d[i];
        r.d[i]=cur/m;
        rem=cur%m;
    }
    r.trim();
    return r;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long N;
    cin>>N;
    long long n=2*N;
    long long r=N;
    Big res(1);
    for(long long i=1;i<=r;i++){
        res=mulSmall(res,n-r+i);
        res=divSmall(res,i);
    }
    res=divSmall(res,N+1);
    cout<<res.d.back();
    for(int i=(int)res.d.size()-2;i>=0;i--){
        cout<<setw(4)<<setfill('0')<<res.d[i];
    }
    cout<<"\n";
    return 0;
}
树屋阶梯

正文

一本通·提高篇的其它内容
