백준 11401번 [이항 계수 3](C++) -yes6686- 티스토리

백준 문제 풀이: 11401 [이항 계수 3]

---

문제 링크: https://www.acmicpc.net/problem/11401

문제 설명:

정수 n과 r이 주어질 때, 이항 계수 C(n, r)을 10⁹+7로 나눈 나머지를 구하는 문제입니다. 이항 계수는 다음과 같이 정의됩니다:

• C(n, r) = n! / (r!(n-r)!)

모듈러 연산과 페르마의 소정리를 사용하여 효율적으로 계산해야 합니다.

---

문제 해결 코드

#include <iostream>
#define MOD 1000000007
using namespace std;

// 거듭제곱을 계산하는 함수 (모듈러 역원 구하기)
long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

int main() {
    int n, r;
    cin >> n >> r;

    if (r == 0 || n == r) {
        cout << 1 << '\n';
        return 0;
    }

    // n! 계산
    long long factorial_n = 1;
    for (int i = 2; i <= n; i++) {
        factorial_n = (factorial_n * i) % MOD;
    }

    // r! 및 (n-r)! 계산
    long long factorial_r = 1, factorial_nr = 1;
    for (int i = 2; i <= r; i++) {
        factorial_r = (factorial_r * i) % MOD;
    }
    for (int i = 2; i <= n - r; i++) {
        factorial_nr = (factorial_nr * i) % MOD;
    }

    // (r! * (n-r)!) % MOD 계산
    long long denominator = (factorial_r * factorial_nr) % MOD;

    // 모듈러 역원 계산
    long long denominator_inverse = mod_pow(denominator, MOD - 2, MOD);

    // 결과 계산
    long long result = (factorial_n * denominator_inverse) % MOD;

    cout << result << '\n';

    return 0;
}

---

페르마의 소정리와 모듈러 역원

페르마의 소정리(Fermat's Little Theorem)는 다음과 같은 내용을 포함합니다:

• 소수 p와 임의의 정수 a에 대해, a^p ≡ a (mod p)가 성립합니다.
• a와 p가 서로소라면, a^(p-1) ≡ 1 (mod p)가 성립합니다.

이를 활용해 모듈러 역원을 계산할 수 있습니다:

• n! / (r!(n-r)!) mod p를 계산하기 위해 (r!(n-r)!)의 역원을 구해야 합니다.
• (r!(n-r)!)^-1 mod p ≡ (r!(n-r)!)^(p-2) mod p로 변환하여 계산합니다.

---

코드 설명

• 핵심 알고리즘: 페르마의 소정리를 사용하여 모듈러 역원을 구한 뒤, 이항 계수를 계산합니다.
• 구현 세부사항:
  • 팩토리얼 값(n!, r!, (n-r)!)을 계산
  • 모듈러 역원을 계산하기 위해 거듭제곱을 사용
  • 최종 결과: n! * (r! * (n-r)!)^-1 mod p
• 시간 복잡도 분석: O(n + log(MOD))
  • 팩토리얼 계산: O(n)
  • 모듈러 역원 계산 (거듭제곱): O(log(MOD))

---

결과

페르마의 소정리를 사용해 효율적으로 이항 계수를 계산합니다. 모듈러 연산과 거듭제곱을 활용하여 큰 숫자 계산 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!