nCr을 오버플로우 없이 구하기

Posted by 0xrgb
2015.02.19 01:43 Code/Algorithm

$ _nC_r $를 구해야 할 때가 있다. DP를 사용하면 쉽게 구할 수 있다.

#include <iostream>
using namespace std;

int dp[105][105]; // R <= N <= 100

int ncr(int N, int R) {
    if( R == 0 ) return 1;
    else if( R > N/2 ) return ncr(N, N-R);
    else if( dp[N][R] ) return dp[N][R];

    return dp[N][R] = ncr(N-1,R-1) + ncr(N-1,R);
}

int main() {
    cout << ncr(45, 6) << endl; // Lotto
    return 0;
}

코드 확인 : http://ideone.com/zWvRUN

이 때, 계산 복잡도는 $ O(nr) $이다.

$ \bmod{p} $가 필요한 경우, 루카스 정리를 이용하면 된다.

이 댓글을 비밀 댓글로