[c++][백준 11401] 이항 계수 3

백준 11401번: 이항 계수 3 [Gold 1]
https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

문제 풀이

• 이 문제는 주어진 두 수의 이항 계수를 구하여 1,000,000,007(MOD)로 modulo 연산 후 출력해야 한다. 하지만 입력 값의 범위가 크기 때문에 이항 계수 값을 구한 후 modulo 연산을 하게 되면 잘못된 값이 나오게 된다.
• 또한 매 연산에서 modulo 연산을 해주면 될 것 같지만 이항 계수는 다음 식과 같이 나눗셈 연산이 들어가기 때문에 불가능하다. modulo 연산의 분배 법칙은 덧셈, 뺄셈, 곱셈에만 적용되기 때문이다.

이항 계수

modulo 연산 분배법칙 나눗셈에 적용 불가

• 이항 계수 식을 정리하면 다음과 같다.

분모, 분자 A, B로 치환

• 이 문제를 해결하기 위해 페르마의 소정리 개념을 사용해야 한다. 페르마의 소정리는 다음과 같다.

• 페르마의 소정리를 이용하여 modulo 연산의 분배 법칙을 사용하기 위해 위의 마지막 식으로 다음의 식을 바꿔준다.

• 위의 오른쪽 식을 코드로 구현했다.

코드

#include <iostream>

using namespace std;

#define MOD 1000000007

long long pow(long long n, long long k) {
    long long ret = 1;
    
    while(k) {
        if(k % 2) ret = (ret * n) % MOD;
        
        n = (n * n) % MOD;
        k /= 2;
    }
    
    return ret;
}

int main() {
    int n, k;
    cin >> n >> k;
    
    long long A = 1, B = 1;
    
    for(int i=n; i>=n-k+1; --i) A = (A * i) % MOD;
    for(int i=2; i<=k; ++i) B = (B * i) % MOD;
    
    cout << (A * pow(B, MOD-2)) % MOD;
    
    return 0;
}

실행 결과