【題解】ZeroJudge d837: NOIP2003 3.栈

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d837
【解題想法】卡特蘭數(Catalan numbers)的應用【參考

  • n = 1, (1)
  • n = 2, (1, 2), (2, 1)
  • n = 3, (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 2, 1)
#include <iostream>
using namespace std;

long long catalan(int n){
    // 2nCn / (n+1)
    long long ret = 1;
    for (int i = 1; i <= n; i++){
        ret *= (2*n - i + 1);
        ret /= i;
    }
    return ret / (n+1);
}

int main() {
    int n;
    while (cin >> n) cout << catalan(n) << "\n";
    return 0;
}
分享本文 Share with friends