G32 卡特兰数

#include <bits/stdc++.h> 
using namespace std;
typedef unsigned long long LL;
int n, m, a[110], b[110];
LL gcd(LL x, LL y) { if (y == 0) return x; else return gcd(y, x % y); }
LL cal(LL n, LL m)
{
    m = min(m, n - m);
    LL s = 1;
    for (int i = 1; i <= m; i++) a[i] = n - i + 1, b[i] = i;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            LL d = gcd(a[i], b[j]);
            a[i] /= d;
            b[j] /= d;
        }
        s *= a[i];
    }
    return s;
}
int main()
{
    int n; scanf("%d", &n);
    LL ans = cal(2 * n, n) / (n + 1);
    printf("%lu", ans);
    return 0;
}