이항계수 (nCr) mod p 계산하기

nCr = n! / (n-r)! * r! 일 때, nCr mod prime을 빠르게 계산하는 방법에 대해서 얘기하려 한다. nCr 한 쿼리는 O(1)에 처리되어야 한다고 가정한다. (즉 전처리 한번 한 이후 nCr을 하나 계산하는데 O(1))

1. O(n^2)

위에 저 식을 그냥 구현만 해도 O(n) 인데..! 하지만 컴퓨터의 메모리는 한정되어 있으니 수를 그대로 들고 갈 수는 없고, mod p는 나눗셈을 하기 썩 좋은 상황은 아니다.

그래서, nCr = (n-1)C(r-1) + (n-1)Cr 이라는 점화식(파스칼의 삼각형)을 사용해서 n^2에 계산하는 게 잘 알려져 있다. N^2 크기의 배열을 잡고 서서히 계산해 나가는 것이다. 이 방법은 나눗셈을 완전히 우회하는 방법으로써 사실 여러모로 제일 안정적인 방법임. 시간 복잡도가 상당히 비효율적이지만.. 암튼 좋다.

2. O(nlgp)

페르마의 소정리에 의해서 a ^ (p-1) == 1 (mod p) 이며, 이를 응용하면 a ^ (p - 2) == a ^ -1 (mod p) 임을 쉽게 알 수 있다. 이것을 사용하면 mod p에서 나눗셈을 할 수 있다.

고로 나눗셈을 하는 건 문제가 안되고... 나눗셈을 빠르게 해야 하는데..? a ^ (p - 2) (mod p) 를 얼마나 빠르게 계산할 수 있지?
 O(p)보다 빠르게 할 수 있나?? 라고 하면, 단순한 분할 정복으로 할 수 있다. https://en.wikipedia.org/wiki/Exponentiation_by_squaring 굳이 nCr이 아니더라도 진짜진짜 많이 쓰이는 방법이니까 꼭 익혀두자.

아무튼 나눗셈이 O(lgp)에 해결됐으니 이제 하나 구하는데 O(nlgp)..? 쿼리 여러개 들어오면 조금 답이 없다. 다행이도 이는 간단한 전처리로 해결할 수 있다. O(n)에 팩토리얼 0! ..... n! (mod p) 을 전처리 해놓고, 이 배열을 토대로 팩토리얼 인버스 역시 O(nlgp)에 전처리 해놓는다. 이제 답은 (n!) * (n-r!)^-1 * (r!)^-1. 하나당 O(1)이다.

3. O(n  + lgp)

nlgp도 빠르지만 이것보다 빠르게 인버스 배열을 계산해야 할 수도 있다. 사실 n + lgp는 엄청 간단한 방법이 있는데, n!의 인버스를 처음에 lgp에 계산해 놓고 반대로 계산하는 방법이다. 생각해보면 (n-1!)^-1 == n * (n!)^-1 이니까 n!의 인버스만 알면 인버스 배열 역시 O(n)에 채울 수 있다. 고로 O(n + lgp)에 모두 계산 가능.

4. O(n)

lgp정도 상관없다고 생각할 수 있는데... O(n) 방법이 코드도 짧고 논리도 상당히 흥미로워서 꼭 익혀두길 바란다. 정수 i에 대한 역원을 아주 간단한 동적 계획법으로 해결할 수 있다. 역원 알면 팩토리얼로 묶는건.. 뭐 쉽다.

* inv(1) = 1

* inv(i) = -(p / i) * inv(p % i)

증명 역시 짧다.

p = p / i * i  + p % i.

-p / i * i = p % i.

inv(i) = inv(p % i) * (-p / i).

이게 역원 구하는 것보다 코딩 훨씬 깔끔한거 같으니 앞으론 이걸로 꿀빨자.

여담으로 3번과 4번 방법은 http://apps.topcoder.com/forums/?module=Thread&threadID=680416&start=15&mc=26 가 원본이다.

5. O((n+p)lgn)

n과 p가 적당히 작다면 소인수분해를 통해서 간단하게 문제를 해결할 수 있다.

수를 2^k * 3^m 과 같은 소인수의 곱으로 표현하자. 이는 cnt[N] 배열을 잡으면 쉽게 가능하다.

이제 곱하는 것과 나누는 것은 소인수분해를 하면서 자연스럽게 처리할 수 있다. 초기에 에라토스테네스의 체를 만들때 low[p] = p의 가장 작은 소인수라고 정의하자.

저러한 테이블이 있으면 while(p > 1) cnt[low[p]]++, p /= low[p] 와 같은 식으로 곱셈을 처리할 수 있다. 나눗셈 역시 동일하다.

이제 cnt[N]을 잘 다루면 O((n + p)lgn)에 문제가 해결된다.

6. O(p)

lucas theorem이라고 p가 작고 n이 클때 유용한 공식이 있다.

https://ko.wikipedia.org/wiki/%EB%A4%BC%EC%B9%B4%EC%9D%98_%EC%A0%95%EB%A6%AC

쿼리당 O(lgN / lgP)인데 뭐 사실상 무시할 만 하다. 어렵지 않으니 외워두자.