Combinatorics in PS

이항 계수의 공식은 다음과 같다.

$$
\binom{n}{r} = \frac{n!}{(n-r)! , r!}
$$

하지만 모듈러 연산이 포함되어 있다. 이전에 배운 모듈러 역원을 이용해 다음과 같이 바꿔서 계산할 수 있다.

$$
\binom{n}{r}
=
n! \cdot ((n-r)!)^{-1} \cdot (r!)^{-1}
\pmod{M}
$$

핵심은 다음 세 값을 빠르게 구하는 것이다.

• $n!$
• $((n-r)!)^{-1}$
• $(r!)^{-1}$

어떻게 구할 수 있을까?

팩토리얼 전처리

먼저 모든 팩토리얼 값을 미리 구해 두자.

$$
fac[i] = i! \pmod{M}
$$

이제 각 팩토리얼의 모듈러 역원도 필요하다.

$$
inv[i] = (i!)^{-1} \pmod{M}
$$

가장 먼저 최댓값에 대한 팩토리얼의 역원을 구해보자.

$M$이 소수라면 페르마의 소정리에 의해

$$
fac[MAX]^{-1}
\equiv
fac[MAX]^{M-2}
\pmod{M}
$$

가 성립하므로, 빠른 거듭제곱을 이용해 $inv[MAX]$를 구할 수 있다.

그 다음에는 이 값을 이용해 나머지 역팩토리얼들을 거꾸로 채워 나간다.

$inv[MAX]$는 $fac[MAX]$의 모듈러 역원이므로, $inv[i]$에 $i$를 곱하면 $inv[i-1]$이 된다. 이를 이용해 모든 팩토리얼 값의 역원을 저장할 수 있다.

$$
inv[i-1] = inv[i] \cdot i \pmod{M}
$$

결과적으로 $fac[i] = i!$와 $inv[i] = (i!)^{-1}$를 모두 미리 구해 둘 수 있고, 이항 계수는 다음과 같이 즉시 계산할 수 있다.

$$
\binom{n}{r}
=
fac[n] \cdot inv[n-r] \cdot inv[r]
\pmod{MOD}
$$

이 방법을 사용하면 전처리는 $O(N + \log(MAX))$, 즉 $O(N)$에 끝나고, 이후 각 조합값은 $O(1)$에 구할 수 있다.

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

inv[MAX] = power(fac[MAX], MOD - 2);

for (int i = MAX; i > 0; i--)
    inv[i-1] = (inv[i] * i) % MOD;

LL comb(LL a, LL b) {
    return (((fac[a] * inv[a-b]) % MOD) * inv[b]) % MOD;
}