조합과 모듈러 연산

nCr은 n이 커질수록 기하급수적으로 커져, 알고리즘 문제에서 1000000007와 같은 소수로 나눈 나머지를 구하게 됩니다.

Dynamic Programming

nCr = n-1Cr-1 + n-1Cr입니다.

#define SIZE 1000
#define DIV 1000000007
static long long DP[SIZE + 1][SIZE + 1];
static int combi(int n, int r) {
    if (!DP[n][r]) {
        if (r == 0 || n - r == 0) DP[n][r] = 1;
        else {
            DP[n][r] = (combi(n - 1, r - 1) + combi(n - 1, r)) % DIV;
        }
    }
    return DP[n][r];
}

전처리의 시간 복잡도는 DP 테이블을 다 채우는데 걸리는 O(n^2)입니다.

페르마의 소정리

Fermat's little Theorem
p가 소수이면, 모든 정수 a에 대해 a ^ p ≡ a (mod p)이다.

p가 소수이고 a가 p의 배수가 아니면, a * a ^ (p - 2) ≡ 1 (mod p)입니다.
따라서, b / a ≡ b / a * a * a ^ (p - 2) ≡ b * a ^ (p - 2) (mod p)입니다.

nCr = n! / (r! * (n - r)!)
≡ n! * (r! * (n - r)!) ^ (p - 2) (mod p)
≡ n! * r! ^ (p - 2) * (n - r)! ^ (p - 2) (mod p)

#define SIZE 1000
#define DIV 1000000007
static long long FAC[SIZE + 1], INV[SIZE + 1];
static long long pow(long long x, long long y) {
    long long result = 1;
    while (y > 0) {
        if (y & 1) result = result * x % DIV;
        x = x * x % DIV;
        y >>= 1;
    }
    return result;
}
static void init() {
    FAC[0] = 1;
    for (int i = 1; i <= SIZE; i++) FAC[i] = (FAC[i - 1] * i) % DIV;
    INV[SIZE] = pow(FAC[SIZE], DIV - 2);
    for (int i = SIZE - 1; i >= 0; i--) {
        INV[i] = (INV[i + 1] * (i + 1)) % DIV;
    }
}
static int combi(int n, int r) {
    if (!FAC[0]) init();
    long long tmp = INV[r] * INV[n - r] % DIV;
    return FAC[n] * tmp % DIV;
}

전처리의 시간 복잡도는 FAC, INV 테이블을 다 채우는데 걸리는 시간 + pow 연산 시간 O(n + logp)입니다.

참고 및 출처
https://ryulstory.tistory.com/62