11401번: 이항 계수 3

https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

N과 K의 범위가 매우 크므로 페르마의 삼각형을 사용할 수는 없으므로, 이항계수 nCk = n! / (k! * (n - k)!)를 이용해야 한다. 단 n!, k!, (n - k)! 역시 매우 큰 값이므로, 각각을 MOD = 1,000,000,007로 나눈 값을 저장해야 한다.

각 팩토리얼을 한 값에 모듈러 연산을 취했기 때문에, n! / (k! * (n - k)!) 공식을 그대로 이용할 수는 없다. 따라서 페르마의 소정리, 즉 소수 p와 p의 배수가 아닌 자연수 a에 대해, a ^ (p - 1) ≡ 1 (mod p)를 이용해야 한다. a를 p - 1, 즉 MOD번 제곱한 값이 1이 되므로, a ^ (p - 2)는 a에 대한 곱셈의 역원이 된다.

k!와 (n - k)!를 MOD로 나눈 값 kf, nkf는 MOD의 배수가 아니므로 kf * nkf 역시 MOD의 배수가 아니므로, 페르마의 소정리에 의해 (kf * nkf) ^ (MOD - 2)는 (kf * nkf)에 대한 곱셈의 역원, 즉 1 / (kf * nkf)와 같다. 따라서 이 값을 N!을 MOD로 나눈 값 nk와 곱해 MOD로 나누면 구하고자 하는 값을 얻을 수 있다.

#include <cstdio>

typedef unsigned long long ull;

#define MOD 1000000007

// (N ^ (MOD - 2))를 구하는 함수
ull pow(ull N) {
    // a: N의 2 ^ k승, ans: N ^ (MOD - 2)를 저장할 공간
    ull a = N % MOD, ans = 1;

    // x를 이진법으로 보았을 때 x의 각 자리에 대해
    for (int x = MOD - 2; x; x /= 2) {
        // 현재 자리가 1이라면 ans에 a를 곱한다
        if (x % 2) ans = (ans * a) % MOD;
        // a를 제곱한다
        a = (a * a) % MOD;
    }

    // N을 (MOD - 2)제곱한 결과를 반환
	return ans;
}

int main() {
    // 이항 계수의 N, K
    int N, K;
    // nf: N!, kf: K!, nkf: (N - K)!
    ull nf = 1, kf = 1, nkf = 1;
    
    // N과 K를 읽어들인다
	scanf("%d %d", &N, &K);
    
    // N!, K!, (N - K)!를 MOD로 나눈 나머지를 구한다
    for (ull i = 2; i <= N; i++) {
        nf = (nf * (i % MOD)) % MOD;
        if (i == K) kf = nf;
        if (i == N - K) nkf = nf;
    }

    // N!과 K!, (N - K)!를 구한 값을 MOD로 나눈 나머지만 알고 있으니
    // 일반적인 이항 계수처럼 계산할 수 없다
    // 페르마의 소정리, 즉 소수 p에 대해 a ^ (p - 1) = 1 (mod p)에 따라
    // (K! * (N - K)!) ^ (MOD - 2) % MOD = 1 / (K! * (N - K)!)이므로
    // 이 결과를 계산해 N!과 곱한 값을 반환
    printf("%lld\n", (nf * pow(kf * nkf)) % MOD);

	return 0;
}