[ 백준 ] 11402번 - 이항 계수 4 (C++)

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

11402번: 이항 계수 4

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 걸 추천드립니다.

 

https://rudalsd.tistory.com/426

 

1.  $_{n}\textrm{C}_{r} =\,    _{n-1}\textrm{C}_{r-1} +\,  _{n-1}\textrm{C}_{r}$ 이므로 분할정복을 이용하여 $_{n}\textrm{C}_{r}$를 구해줍니다.

 

2. 뤼카의 정리를 이용하여 각각의 조합의 값들을 곱해 M으로 나눈 나머지를 출력합니다.

 

[ 소스 코드 ]

#include<iostream>
#include<vector>
#define ll long long
 
using namespace std;
 
ll N, K;
int M;
ll arr[2001][2001];
 
vector<int> luca(ll N, int M)
{
    vector<int> ret;
 
    while (N) {
        int temp = N % M;
        ret.push_back(temp);
        N /= M;
    }
 
    return ret;
}
 
ll comb(int N, int R)
{
    if (N < R) return 0;
    if (R == 1) return N;
    if (R == 0) return 1;
    if (arr[N][R] != 0) return arr[N][R];
 
    return arr[N][R] = (comb(N - 1, R - 1) + comb(N - 1, R)) % M;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> K >> M;
 
    vector<int> n, k;
 
    n = luca(N, M);
    k = luca(K, M);
 
    int idx = min(n.size(), k.size());
 
    ll ans = 1;
 
    for (int i = 0; i < idx; i++) {
        ans *= comb(n[i], k[i]);
        ans %= M;
        if (ans == 0) break;
    }
 
    cout << ans;
}