P1044 잔로골(수론)(카틀란수)

카틀란수 추이 공식 중 하나(오늘 막 알았는데...): f[n]= f[n-1]*(4*n-2)/(n+1)(Ps: 몇몇 데이터가 까다로운 문제에서 이 공식에 문제가 생긴다고 들었는데? 그러나 이 문제에 대해서는 이 공식이 유용하다) 코드는 다음과 같다.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long

using namespace std ;

int main(){
    ll n ;
    cin >> n ;
    ll f[n+10] ;
    f[0] = 1 , f[1] = 1 ;
    for ( ll i = 2 ; i <= n ; i ++ ){
        f[i] = f[i-1] * (4 * i - 2) / (i + 1) ;
    }
    cout << f[n] << endl ;
    return 0 ;
}

좋은 웹페이지 즐겨찾기