백준 11401번 이항 계수 3

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘 : 수학 (페르마의 소정리)

순열조합 nCk 를 계산하는 문제입니다. n의 최대가 4*10^6 으로 매우 크게 주어졌습니다.

(1) 페르마의 소정리

 

 페르마의 소정리는 위와 같습니다. 

 이를 이용하여 큰 수의 nCk를 계산해줄 겁니다.

(2) Modulo 연산

 Modulo 연산이 새로운 분들은 다음 링크를 참고해 주세요! Modular

 우리가 생각해야 하는 점은, 

 Modulo치고 연산하는 것이 곱셈, 덧셈에서는 먹히지만 나눗셈에서는 먹히지 않는다는 것입니다...

(3) 수학

 nCk 는 위와 같습니다. 이때 분자 분모가 팩토리얼로 long long 범위를 넘어가서 문제가 됩니다. 

 modulo를 쳐주고 싶은데 과정(2)에서 말씀드린 것과 같이 나눗셈에서는 modulo를 못칩니다.

 

 따라서 과정(1)의 페르마의 소정리를 이용하여 다음과 같이 계산해 주는 겁니다.

 이에 따라 우리가 구하고자 하는 nCk는 다음과 같습니다.

 

 즉 우리가 구하고자 하는 답은 다음과 같습니다.

 과정(2)에서 말씀드린 것과 같이 곱셈에서는 Modulo를 치면서 연산해도 됩니다.

(4) 코드 8~31

 k!^(MOD-2) (k!의 역원) 을 계산하는 함수를 만들어 줍니다.
 k! 을 구한 후 MOD-2 제곱을 2진법을 활용하여 구현했습니다.

(3) 코드 32~40

 n*(n-1)*..*(n-k+1) 을 계산하는 함수를 만들어 줍니다.

(4) 코드 44~46

 과정(2), (3) 에서 구한 두 값을 곱하면 구하고자 하는 답입니다.