bcatalan.cpp

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define vi vector<int>
#define ii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define stoi stoll
#define popcnt __builtin_popcount
#define getbit(x, k) ((x >> k) & 1)
#define all(x) (x).begin(),(x).end()
#define FOR(i,j,k) for(int i=j; i<k; i++)
#define look(a) cerr <<#a<<": "<<a<<endl;
#define look2(a,b) cerr <<#a<<": "<<a<<" | "<<#b<<": "<<b<< endl;

const int BASE = 1e4;

void fix(vi &a){
    a.push_back(0);
    FOR(i,0,a.size()-1){
        a[i+1] += a[i] / BASE;
        a[i] %= BASE;
        if (a[i] < 0){
            a[i] += BASE;
            a[i+1]--;
        }
    }
    while (a.size() >= 2 && a.back() == 0) a.pop_back();
}

vi operator*(const vi &a, const vi &b){
    vi c(a.size() + b.size() + 1);
    FOR(i,0,a.size())
        FOR(j,0,b.size()){
            c[i+j] += a[i]*b[j];
            c[i+j+1] += c[i+j] / BASE;
            c[i+j] %= BASE;
        }
    return fix(c), c;
}

vi to_vi(int x){
    assert(x < BASE);
    return vi(1,x);
}

vi operator+(vi a, const vi &b){
    a.resize(max(a.size(), b.size()));
    FOR(i,0,b.size())
        a[i] += b[i];
    return fix(a), a;
}

vi operator*(vi a, int x){
    assert(x < BASE);
    FOR(i,0,a.size())
        a[i] *= x;
    return fix(a), a;
}

vi operator/(vi a, int x) {  // x < BASE
    assert(x < BASE);
    for (int i = (int)a.size() - 1, r = 0; i >= 0; --i, r %= x) {
        r = r * BASE + a[i];
        a[i] = r / x;
    }
    return fix(a), a;
}

ostream &operator<<(ostream &cout, const vi &a) {
    cout << a.back();
    for (int i = (int)a.size() - 2; i >= 0; i--)
        cout << a[i];
    return cout;
}

void solve()
{
    int n;
    cin >> n;

    vi f[n+2];
    f[0] = f[1] = to_vi(1);
    FOR(i,1,n+1){
        // look(i);
        // f[i] = to_vi(0);
        // FOR(j,0,i)
        //  f[i] = f[i] + f[j] * f[i-j-1];
        f[i+1] = (to_vi(4*i-2)*f[i])/(i+1);
    }

    cout << f[n+1];
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
        cout << '\n';
    }
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}