[백준] 11402 이항계수4

이항계수 4까지왔다...!

4에서는 대체 뭘 배울수 있을까

바로 뤼카의 정리다...!

- 뤼카의 정리

위키에는 이렇게 적혀있다

증명을 이해하려했지만 불가능

그래서 난 뤼카가 정리해준것만 받아먹을 예정이다

정리하자면 nCr(mod d)가 있을때

n과 r을 d진법으로 나타낸다 이 때

nCr = 모든 niCri의 곱(0<= i <= k)이다 ㅎㅎ

근데 만약 ni<ri라면 niCri가 0이므로 nCr도 0이된다..!

n과m이 너~~~~~무 크므로 우린 이걸 이용한다

구현을 쉽게하는 방법은 미리 이항계수를 구해두고

binomial[n%mod][r%mod] 를 곱해주는 것이다!

n과 r은 다음자리를 볼 수 있게 계속 mod로 나눠준다

뤼카덕에 문제도 풀고 좋다 ㅎㅎ 뤼카랑 친하게 지내기 ㄱ

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
ll d[2020][2020], n, r, mod;
ll binomial(ll x, ll y) {
    if (x < y) return 0;
    if (y == 0 || y == x) return 1;
    ll&ret = d[x][y];
    if (ret != -1) return ret;
    ret = binomial(x - 1, y - 1) % mod + binomial(x - 1, y) % mod;
    ret %= mod;
    return ret;
}
 
int main() {
    memset(d, -1, sizeof(d));
    scanf(" %lld %lld %lld", &n, &r, &mod);
    ll ret = 1;
    while (n || r) {
        ret *= binomial(n%mod, r%mod);
        ret %= mod;
        n /= mod;
        r /= mod;
    }
    printf("%lld\n", ret);
}