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

2017-06-22 08:53:18 | 조회수 8034


$\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) 빠르게 구하기 - 알고리즘닷컴
14 개의 글