소수 p에 대해 nCr % p(n,r<p) 빠르게 구하기


작성일 : 2017-06-22 08:53:18
조회수 : 5874


본문

$\binom{n}{k} \mod p = (\frac{n!}{k!(n-k!)}) \mod p$ 이므로


n,k의 숫자가 작을 때에는 for문 등을 통해 overflow가 일어나지 않도록 연산을 해 주면서 계산할 수가 있다.


하지만 n,k가 매우 클 때에는 이러한 계산이 불가능하므로 나머지 연산을 이용한다.


$(a*b)\mod p = ((a\mod p) * (b\mod * p)) \mod p$


임을 이용하여 이를 계산할 수 있다. 단, 분모의 경우 지수에 -1이 붙어 있는 상태이므로 계산하기 전 modular inverse를 진행한다.


소수 p에 대해


$a^{p-1} = 1 \mod p$

이고


$a^{p-1} = a * a^{p-2}$ 이므로


$a^{p-2} \mod p$


를 구하면 되고, 제곱 연산은 $a^{2p+1} = a * a^p * a^p$ 의 성질을 이용해 로그 복잡도로 계산 가능하다.


이를 계산하기전 전처리로 fatorial을 p로 나눈 나머지를 미리 계산하여 정리해둔다.


#define MOD 1000000007
ll power(ll a, ll b)
{
    ll x = 1, y = a;
    while (b > 0)
    {
        if (b % 2) x = (x*y) % MOD;
        y = (y*y) % MOD;
        b /= 2;
    }
    return x%MOD;
}
ll inverse(ll n){return power(n, MOD - 2);}
ll nCr(ll n, ll r)
{
    return ((factorial[n] * (inverse(factorial[r]) * inverse(factorial[n - r]) % MOD)) % MOD);
}

//factorial 전처리

factorial[0] = 1;
for (int i = 1; i <= INPUT_MAX; i++) factorial[i] = (factorial[i - 1] * i) % MOD;

소수 p에 대해 nCr % p(n,r<p) 빠르게 구하기 - 알고리즘닷컴
알고리즘 문서에서는 다양한 알고리즘 개념들을 포스팅 하는 곳입니다.