题解 P1754 【球迷购票问题】

2018-05-25 18:03:50


Catalan number(卡塔兰数)

至于为什么是卡塔兰数的,各位dalao已经有解释了

蒟蒻就只说一下卡塔兰数的公式:

f[n] = ∑(i=0 to n-1)f[i]*f[n-1-i]

f[n] = f[n-1]*(4n-2)/(n+1)

f[n] = C(n,2n)/(n+1)

f[n] = C(n,2n) - C(n-1,2n)

蒟蒻用的第二种:

#include <bits/stdc++.h>
using namespace std;
int n;unsigned long long catalan[30];
unsigned long long calc(int n)
{
    if (n == 1) return 1;
    if (catalan[n]) return catalan[n];
    catalan[n] = calc(n - 1) * (4 * n - 2) / (n + 1);
    return catalan[n];
}
int main ()
{
    cin >> n;
    cout << calc(n); 
    return 0;
}