题解 P1754 【球迷购票问题】
SIGSEGV
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)
蒟蒻用的第二种：
```cpp
#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;
}
```