이항계수를 구하는 알고리즘

이항계수 는   으로 정의되며 흔히 조합으로 알려져 있습니다.

n개의 원소를 가지는 집합에서 k개의 부분집합을 고르는 조합의 경우의 수를 이항계수라고 합니다.

우리는 이항계수가 가지는  이라는 성질을 이용하여 메모제이션 해주어 O(N^2)의 시간과 메모리 복잡도를 가지는 전처리 한번으로 매 쿼리를 O(1)에 처리해줄 수 있습니다.

하지만 BOJ)11401 이항 계수 3 처럼 N이 큰 쿼리가 들어올 경우 O(N^2)의 방법으로는 해결할 수 없습니다.

그래서 개선된 방법을 필요로 합니다.

이는 맨 위에 정의 된 를 이용하는 방법입니다.

문제 조건에서 모듈러를 위한 소수가 주어질텐데  을 소수에 대한 의 역원을 구해주는 문제로 수정하여 해결하는 문제입니다.

우리는 동적 프로그래밍을 이용하여 n!을 계산하는데 O(N)의 시간 복잡도를 가지게 됩니다.

이제 소수 에 대한 의 역원을 구해주어야 하는데 이는 페르마의 소정리와 분할정복을 이용하여 O(log)의 시간에 해결 가능합니다.

페르마의 소정리는  라는 수식인데 이를  로 변형하여가 를 만족하는 가 되어 역원이 라고 정의됩니다.

그러므로 우리는 의 제곱에 을 곱해줌으로서 답을 구해줄 수 있습니다.

의 제곱은 분할 정복을 이용하여 O(log)시간에 계산해 줄 수 있습니다.

#define P 1000000007LL
ll power(ll x, ll y) {    //분할 정복을 이용하여 x^y 구하기
    ll ret = 1;
    while (y > 0) {
        if (y % 2) {
            ret *= x;
            ret %= P;
        }
        x *= x;
        x %= P;
        y /= 2;
    }
    return ret;
}

전체 시간 복잡도는 총 O(N*logP)가 되겠군요.

쿼리가 여러번 들어올 경우를 대비하여 n!을 O(N)의 시간에 전부 계산해 준 뒤 N개의 수에 대해서 n!의 inverse를 각각 O(log P) 시간에 전처리 해주면 총 O(N+NlogP)의 시간에 전처리가 가능하고 전처리 후에는 쿼리마다 O(1)의 시간에 처리가능 합니다.

자 여기서 더 개선이 가능할까요?

놀랍게도 O(N+logP)의 시간 복잡도에 이항계수 계산의 전처리가 가능합니다.

저도 구사과님의 블로그를 통하여 알게 된 방법인데요.

n * inverse(n!) = inverse((n-1)!) 라는 수식을 이용하여 (N!)의 inverse만 분할정복을 통하여 O(logP)의 시간에 한번 구해준다면 메모제이션을 통하여 n!의 inverse를 O(N) 시간에 처리 가능합니다.

따라서 O(N+logP)의 시간 복잡도에 이항계수 계산의 전처리가 가능합니다.

이어서 범위 내의 쿼리를 O(1)의 시간 복잡도에 처리해줄 수 있습니다.

다음은 BOJ)11401 이항 계수3 의 소스코드 입니다.

#include <cstdio>
#include <algorithm>
#define P 1000000007LL
typedef long long ll;
using namespace std;
ll fac[4000001], n, k, inv[4000001];//inv[x]의 정의는 x의inverse가 아닌 x!의 inverse
ll power(ll x, ll y) {    //분할 정복을 이용하여 x^y 구하기
    ll ret = 1;
    while (y > 0) {
        if (y % 2) {
            ret *= x;
            ret %= P;
        }
        x *= x;
        x %= P;
        y /= 2;
    }
    return ret;
}
int main() {
    fac[1] = 1;
    for (int i = 1; i <= 4000000; i++)
        fac[i] = (fac[i - 1] * i) % P;            //factorial 전처리
    inv[4000000] = power(fac[4000000], P - 2);    //페르마의 소정리를 이용하여 fac(400만)의 inverse를 구함(이때 분할 정복을 이용하여 logP의 시간에 처리) 
    for (int i = 4000000 - 1; i >= 0; i--) 
        inv[i] = (inv[i + 1] * (i + 1)) % P;    //inverse(fac(i))=inverse(fac(i+1))*(i+1)이라는 수식을 이용하여 전처리
    //총 O(N+logP)시간에 전처리를 끝냄 
    //전처리가 끝났기 때문에 어떤 쿼리가 들어와도 상수시간에 이항 계수를 계산 가능
    scanf("%lld%lld", &n, &k);
    if (n == k || !k) {
        puts("1");
        return 0;
    }
    ll r = (fac[n] * inv[n - k]) % P;
    r = (r*inv[k]) % P;
    printf("%lld\n", r);
    return 0;
}

자 이제 이항계수를 활용한 여러 문제들을 풀어봅시다.