[백준] 13977번 : 이항 계수와 쿼리

안녕하세요 aim_higher 입니다.

백준 13977번 : 이항 계수와 쿼리 코드리뷰입니다.

---

Baekjoon Online Judge 11758번: CCW

https://www.acmicpc.net/problem/13977

• Number Theory(정수론)

문제가 정말 짧네요. nCk를 1,000,000,007로 나눈 나머지를 구하는 문제입니다.

쿼리가 총 M개(M ≤ 100,000), N과 K가(N ≤ 4,000,000, K ≤ N)으로 주어지므로

일반적인 메모이제이션과 재귀를 이용한 방법으로는 TLE를 받게 됩니다

---

해결기법은 다음과 같습니다

우선, 옛날에 배웠던 조합의 성질을 더듬어보며 다음의 식을 떠올립니다.

nCr = n! / r! * (n-r)!

nCr이 모두 x! 와 같은 팩토리얼의 형태로 변환되는 것을 알 수 있습니다.

N의 범위(N ≤ 4,000,000)까지 x! / MOD 값을 미리 구해 놓고 위의 식대로 곱하자는 생각을 합니다.

그런데 r!*(n-r)!은 역수 형태라 MOD로 나눈 나머지를 취하면 안될 것 같다는 생각이 듭니다...

그러면 나눗셈이 아닌 일반적인 곱셈으로 바꿀 수 있는 방법은 없을까요?

 

이때 사용되는 것이 "페르마의 소정리" 입니다.

$$a^{\rho}\equiv1(\bmod\rho)$$

이 수학식을 우리가 작성하는 코드로 변환하면

$$a^{\rho-1} \text{% } \rho =1$$

우리가 사용할 수 있도록 양변을 a로 나누면

$$a^{\rho-2} \text{% } \rho =a^{-1}$$

우변의 \(a^{-1}\) 역수꼴을 좌변으로 바꿀 수 있다는 걸 알게 됐습니다.

a에 r!*(n-r)!을 대입하고, p에 MOD(1,000,000,007)을 대입하면

$$(r!*(n-r)!)^{MOD-2} \text{% } MOD =(r!*(n-r)!)^{-1}$$

이와 같이 지수 곱셈 형태로 나옵니다.

지수 곱셈은 다음 코드처럼 실행하시면 됩니다.

ll powExp(ll a, ll x){
    if (x == 1) return a % MOD;
    if (x % 2) return powExp(a, x - 1) * a % MOD;
    return powExp(a * a % MOD, x / 2);
}

핵심은 지수가 짝수일때 반으로 쪼개서 재귀로 해결합니다

이런 코드는 직관적으로 생각하면 O(logN)입니다.

팩토리얼 전처리를 모두 수행했으니 지수곱셈에 인자로 전달되는 팩토리얼은 O(1)

 

요약하자면 조합 공식 + 페르마의 소정리 + 지수 곱셈 입니다.

위 세가지를 잘 기억해서 더 어려운 문제가 나왔을 때 응용해봅시다.