[C++] 백준 11402 : 이항 계수 4 / 뤼카의 정리

1. 문제 출처

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

11402번: 이항 계수 4

 

 

2. 문제 접근

$10^{18}$ 이하의 자연수 $n$과 $n$ 이하의 음이 아닌 정수 $k$가 주어졌을 때, $_nC_k$의 값을 구하는 문제이다. $_nC_k$ 의 값이 매우 커질 수 있으므로, 2000 이하의 임의의 소수 $m$이 주어지고 $_nC_k$의 값을 $m$으로 나눈 나머지를 출력하면 된다.

 

 

 

 

이 문제를 해결하기 위해서는 뤼카의 정리에 대해서 알아야 한다. 뤼카의 정리는 $_nC_k$ 를 $m$ 으로 나눈 나머지를 구하고자 할 때 사용할 수 있으며 정확한 동작 원리는 다음과 같다.

 

 

 

$$\binom{n}{r} = \prod_{i=1}^{k}\binom{n_{i}}{r_{i}}\mod p$$

 

 

1. $_nC_k$ 의 $n$ 과 $k$ 를 각각 $m$ 진수로 표현한다.

2. $m$진수로 표현된 두 수를 각 자리수에 맞추어 조합을 계산하고, 이 계산된 조합들을 모두 곱하여 $m$ 으로 모듈러 연산을 취한다.

 

 

 

 

수식만 가지고서는 이해하기 힘들기 때문에 백준의 한 예제를 같이 확인해보자.

 

 

 

$$ \binom{100}{45}\mod 7$$

 

 

 

 

문제에서 주어진 값들은 $n=100, k=45, m=7$ 이다. 먼저 $n$과 \(k\)의 값을 \(m\)진수로 나타내야 한다. 먼저 100을 7진수로 표현하면 202이고, 45를 7진수로 표현하면 63이다.

 

 

n과 k값을 m진수로 변형한 형태

 

 

7진수로 변환한 두 수에 대해서 각 index에 대해서 다시 조합을 한다. 다음과 같이 수식으로 나타낼 수 있다.

 

 

$$\binom{100}{45}\mod 7 = \binom{2}{0}\binom{0}{6}\binom{2}{3} \mod 7$$

 

 

하지만 $_nC_r$의 연산과정에서,  $r$의 값이 $n$보다 커질 수 있는데, 이 경우에 결과값은 0으로 간주한다.

 

 

$$\binom{2}{0}\binom{0}{6}\binom{2}{3} \mod 7 = 1\times0\times0 = 0$$

 

 

 

 

3. 코드

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>

using namespace std;

ll memo[2001][2001]; // memo[i][j] = iCj의 값이 저장
int m;

vector<int> getLuca(ll val, int mod) {
    vector<int> ret;
    while (val > 0) {
        int remainder = val % mod;
        ret.push_back(remainder);
        val /= mod;
    }
    return ret;
}

ll comb(int n, int r) {
    if (n < r) return 0;
    if (n / 2 < r) r = n - r;

    ll &ret = memo[n][r];
    if (ret != -1) return ret;

    if (r == 0) return ret = 1;
    else if (r == 1) return ret = n;

    return ret = (comb(n - 1, r - 1) + comb(n - 1, r)) % m;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    memset(memo, -1, sizeof(memo));

    ll n, k, res = 1;

    cin >> n >> k >> m;

    vector<int> lucaN, lucaK;
    lucaN = getLuca(n, m);
    lucaK = getLuca(k, m);

    int minIdx = min(lucaN.size(), lucaK.size());
    for (int i = 0; i < minIdx; ++i) {
        int n = lucaN[i];
        int r = lucaK[i];

        res = res * comb(n, r);
        res %= m;
    }

    cout << res << "\n";

    return 0;
}

 

 

 

 

4. 참고한 글

https://ko.wikipedia.org/wiki/%EB%A4%BC%EC%B9%B4%EC%9D%98_%EC%A0%95%EB%A6%AC

뤼카의 정리 - 위키백과, 우리 모두의 백과사전

https://bowbowbow.tistory.com/2

Lucas Theorem : 뤼카의 정리