이항계수를 어떤수로 나눴을 때 값 구하기

공부해도 시간지나면 잊어버리니까 지금부터라도 기록해두는게 좋을것같다.

(이 내용은 제가 이해한걸 정리해둔 거라 틀린 내용이 있을 수도 있습니다.)

 

이항계수는 nCk = (n-1)C(k-1) + (n-1)Ck 의 점화식으로 계산할 수 있다.

그 값을 구해서 p로 나눈다고 하면 답은 nCk % p 가 되고,

위의 과정은 O(n^2)의 시간복잡도를 가진다.

 

n과 k의 값이 크면 시간 안에 답을 구할 수 없기 때문에 다음의 두 가지 방법을 사용해야 한다.

(1)페르마 소정리

(2)확장 유클리드 호제법

 

(1)페르마 소정리

위 정의에서 a^(p-1) mod p 는 1 이라 할 수 있고,

a^(p-2) mod p 는 a^(-1) mod p 라고 할 수 있다.

 

nCk를 어떤 소수 p로 나눈 나머지를 구한다고하면

nCk % p = n!/(k!(n-k)!) % p 인데 분모에는 모듈러연산을 쓸 수 없으니까

n!(k!(n-k)!)^(-1) % p로 해주고 (k!(n-k)!)^(-1) = t 라고 했을 때

위의 정의에서 t mod p 를 구하는 것은 (k!(n-k)!)^(p-2) mod p 를 구하는 것과 같다.

따라서 nCk mod p 의 값은 n!(k!(n-k)!)^(p-2) mod p 의 값과 같다고 할 수 있다.

(k!(n-k)!)^(p-2)값은 분할정복으로 O(log(p-2))만에 구할 수 있다.

이 방법으로 값을 구했을 때 시간복잡도는 O(n)이다.

 

(2)확장 유클리드 호제법

유클리드 호제법은 두 정수 a, b 가 있을 때

gcd(a,b)를 구해주는 알고리즘이고 (gcd(a,b) = gcd(b,a%b))

확장 유클리드 알고리즘은 as + bt = gcd(a,b) 일 때 두 정수 (s,t)값도 구해준다.

여기서 n!(k!(n-k)!)^(-1) % p 에서 (k!(n-k)!)^(-1) % p 의 값을 구하면 되는데

곱셈의 역원을 이용해 구할 수 있다. 곱셈의 역원은

두 정수 a, b가 있을 때 ac % n 이 1이면 c는 a의 곱셈역이다.

베주 항등식에서 ax + by = d인데 양변을 y로 나눈 나머지를 보면

ax mod y = d mod y 여기서 a와 b가 서로소라고 하면

ax mod y = 1 mod y 라고 할 수 있다. (gcd(a,b)=1이니까)

그러면 x mod y = a^(-1) mod y 라고 할 수 있다.

여기서 a = k!(n-k)! 라 하면 x 의 값을 구하는 것이 답을 찾는 것이라 할 수 있다.

 

찾는 과정은 확장 유클리드 호제법을 이용하는데

s1=1, s2=0

t1=0, t2=0

r1=a, r2=b (크기상관없고 서로소여야됨) // 초기값 설정

 

--여기서부터 r2=0일때까지 반복--

q=floor(r1/r2)

(s1,s2) = (s2,s1-s2*q)

(t1,t2) = (t2,t1-t2*q)

(r1,r2) = (r2,r1-r2*q)

---------------------------------------

위 반복이 끝나면 (a*s1 + b*t1) mod p = 1 mod p 을 만족하는 (s1,t1)값이 나온다.

(s1,t1)중 음수값이 있을수도 있다. 이해를 돕기위해 예제1

예를들어 n*s1 + k!(n-k)!*t1 = 1 이렇게 식을 두고 계산했다고 하면 t1이 우리가 찾는 값이다.

(n*s1 + k!(n-k)!*t1) mod p = k!(n-k)!*t1 mod p = 1 mod p 이므로

t1 mod p = (k!(n-k)!)^(-1) mod p이다

 

따라서 nCk mod p = n!(k!(n-k)!)^(-1) mod p

= (n! mod p)((k!(n-k)!)^(-1) mod p)

= (n! mod p)(t1 mod p) mod p 라고 할 수 있다.

 

이 방법으로도 O(n)의 시간복잡도를 가진다.

 

(BOJ에서 11401, 14565, 3955, 13977을 풀면서 공부한 내용입니다.)