$\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;