[백준] 11401번: 이항 계수 3 - Kotlin[코틀린]

문제

 

11401번: 이항 계수 3

 

---

풀이

 

 이항 계수를 구하는 공식은 $_{n}\mathrm{C}_{r}=\binom{n}{r}=\frac{n!}{r!(n-r)!}$ 이다. 문제는 여기서 1,000,000,007로 나눈 나머지 값을 출력해야 한다. 주어진 범위가 크기 때문에 재귀 팩토리얼만 활용하면 스택 오버플로우 에러가 발생하고 파스칼 삼각형 dp를 활용하면 시간 초과가 발생한다. 이를 해결하기 위해서 모듈러 연산, 페르마 소정리, 분할 정복을 활용해야 한다.

 

- 모듈러 연산의 분배법칙

 

 (A + B) % p = ((A % p) + (B % p)) % p

 

 모듈러 연산의 분배법칙이란 위의 식이 성립한다는 것인데 이를 증명해보면 다음과 같다. 우선 A와 B를 몫과 나머지로 치환하기 위해 A = a $\times$ p + m, B = b $\times$ p + n로 가정해보자. 이것을 위의 식에 대입하면,

 

 (A + B) % p

 = (a $\times$ p + m + b $\times$ p + n) % p

 = ((a + b) $\times$ p + (m + n)) % p      // A와 B를 치환

 = (m + n) % p                              // % 연산의 특성에 따라 (a+b) $\times$ p는  사라짐

 - > m + n < |p| 라면 나머지는 m + n

      m + n > |p| 라면  m + n 을 d $\times$ p + l로 치환하여 (m + n) % p =  (d $\times$ p + l) % p = l

 

 ((A % p) + (B % p)) % p

 = ((a $\times$ p + m) % p + (b $\times$ p + n) % p) % p   // A와 B를 치환

 = (m + n) % p                                                  // % 연산의 특성에 따라 a $\times$ p, b $\times$ p는 사라짐

 - > m + n < |p| 라면 나머지는 m + n

      m + n > |p| 라면  m + n 을 d $\times$ p + l로 치환하여 (m + n) % p =  (d $\times$ p + l) % p = l

 

 양변이 같으므로 위의 법칙이 증명된다. 이와 비슷한 증명으로 빼기와 곱셈에서도 성립하며 공식은 아래와 같다.

 

 (A - B) % N = ((A % N) - (B % N)) % N
 (A X B) % N = ((A % N) X (B % N)) % N

 

 하지만 나눗셈에서는 이 공식이 성립하지 않아 나눗셈 $\dfrac AB = T$에서 곱셈 $AB^{-1} = T$의 형태로 바꾼 뒤, 곱셈에 대한 모듈러 연산의 분배법칙을 적용한다. 우리가 구하려는 $\frac{n!}{r!(n-r)!}$를 $n!{(r!(n-r)!)}^{-1}$로 바꾸어주면 될 것이다. 여기서 나눗셈을 곱셈의 형태로 바꾸는데는 페르마 소정리 혹은 확장 유클리드 알고리즘을 이용한다.

 

- 페르마 소정리

 

 페르마 소정리는 아래와 같다.

 

 p가 소수이면, 모든 정수 a에 대해 $a^p\equiv a\left({\rm mod}\ p\right)$이다.
 p가 소수이고 a가 p의 배수가 아니면, $a^{p-1}\equiv 1\left({\rm mod}\ p\right)$이다.

 

 $\equiv$ 기호는 합동을 의미하며 p로 나눈 나머지가 서로 같다는 뜻이다.

 

 위의 식을 정리하면  $a\times a^{p-2}\equiv 1\left({\rm mod}\ p\right)$으로 표현할 수 있는데, 이는 $a\left({\rm mod}\ p\right)$에 대한 역원이 $a^{p-2}\left({\rm mod}\ p\right)$라는 것이다. $a$에 우리가 구하려던 ${r!(n-r)!}$ 을 대입해보면

${(r!(n-r)!)}^{-1} = {(r!(n-r)!)}^{1000000007-2}$이 되고, 이제 모듈러 연산의 곱셈 분배법칙을 이용할 수 있게 된다. 최종적으로 구해지는 식은 다음과 같다.

 

 $ \frac{n!}{r!(n-r)!}mod\ p = (n! \times {r!(n-r)!}^{-1})mod\ p = (n! \times {(r!(n-r)!)}^{p-2})mod\ p = ((n! mod\ p) \times ({(r!(n-r)!)}^{p-2})mod\ p)mod\ p$

 

- 분할 정복

 

 이 문제에서 p-2만큼의 거듭제곱 값을 구할 때 분할 정복을 이용한다. 분할 정복이란 $a^n$을 구할 때, n이 1이 될 때 까지 지수를 반으로 나눈 값을 구하여 계산하는 방법으로 식으로 표현하면 다음과 같다.

 

 $a^{8} = a^{4}\times a^{4} = (a^{2}\times a^{2})\times(a^{2}\times a^{2}) \\= ((a^{1}\times a^{1})\times (a^{1}\times a^{1}))\times((a^{1}\times a^{1})\times (a^{1}\times a^{1}))$

 

 여기서 지수가 홀수인 경우에는 지수를 짝수로 만들고 a를 곱한 값에서 실행하면 된다.

 

 $a^{9} = a^{8}\times a = a^{4}\times a^{4}\times a = (a^{2}\times a^{2})\times(a^{2}\times a^{2})\times a \\= ((a^{1}\times a^{1})\times (a^{1}\times a^{1}))\times((a^{1}\times a^{1})\times (a^{1}\times a^{1}))\times a$

 $a^n$을 그대로 연산하면 O(n)의 시간이 필요하지만 분할정복을 이용하면 O(logn)만 사용하면 된다. 

---

코드

 

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val num = st.nextToken().toLong()
    val k = st.nextToken().toLong()
    val mod = 1000000007L

    fun pow(base: Long, expo: Long): Long { // 지수 구하는 함수, base: 밑, expo: 지수
        if (expo == 1L) {
            return base % mod
        }

        val tmp = pow(base, expo / 2) // 구하려던 지수의 절반이 되는 값

        /*
        홀수인 경우 구했던 값의 제곱에 base를 한번 더 곱한 값을 반환 한다.
        짝수인 경우 구했던 값의 제곱을 반환 한다.
         */
        return if (expo % 2 == 1L) {
            tmp * tmp % mod * base % mod
        } else {
            tmp * tmp % mod
        }
    }

    fun factorial(n: Long): Long {
        return if (n <= 1L) 1L
        else (n * factorial(n - 1)) % mod
    }

    val top = factorial(num) // 분자
    val bottom = (factorial(k) * factorial(num - k)) % mod // 분모

    bw.write("${top * pow(bottom, mod - 2) % mod}") // 분자 * 분모의 역원
    bw.flush()
    bw.close()
    br.close()
}