백준 11401 이항 계수 3

www.acmicpc.net/problem/11401

11401번: 이항 계수 3

머리가 아파오는 수학 문제다.

이 문제는 해답을 참고해서 풀었다.

기본적으로 

• 페르마의 소정리를 이용
• 확장 유클리드 호제법을 이용

이외에 소인수 분해로 푸는 방법이 있는 것 같은데, 나는 페르마의 소정리를 이용해서 풀었다.

 

페르마의 소정리는 소수 p와 정수 a에 대해 다음을 만족한다.

 

$$a^{(p-1)}\equiv1\;(mod\;p)$$

 

따라서 $$nCk = \frac{k!}{(n-k)!}$$

 

에서 n! = A, k!(n-k)! = B로 치환한다.

 

우리가 구해야 할 것은 $$AB^{-1}\; \% \;P$$ 인데

 

기본적으로 모듈러 연산은 더하기, 빼기, 곱하기 까진 성립 하지만 나머지에 대해선 성립하지 않는다.

그래서 페르마의 소정리를 이용하여 분수 꼴에서 정수 꼴로 바꾸어 계산한다.

 

 

$$B^{p-1} \; = \;1\;(mod\;P)$$ 이므로

$$B\;*\;B^{p-2}\;=\;1\;(mod\;P)$$ 이고

$$B^{p-2}\;=\;B^{-1}\;(mod\;P)$$ 

$$B^{-1}\;=\;B^{p-2}\;\%\;P$$ 이다

 따라서 

$$(A\%P)(B^{p-2}\%P)\%P $$

임을 알 수 있다.

 

치환했던 것을 풀어보면

$$(N!\%P)((N!(N-K)!^{P-2}\%P))\%P$$

이다.

 

여기까지 구했다면 나머지는 쉽다.

#include <cstdio>
using namespace std;
using ll = long long;
#define MOD 1000000007LL

ll fac[4000001];

void factorial() {
	fac[0] = fac[1] = 1;
	for (int i = 2; i < 4000001; i++) {
		fac[i] = (fac[i - 1] * i) % MOD;
	}
}

ll power(ll a, ll b) {
	if (b == 0) return 1;
	if (b % 2 > 0) return (power(a, b - 1) * a) % MOD;
	ll half = power(a, b / 2) % MOD;
	return half * half % MOD;
}

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	if (n == k || k == 0) {
		printf("1"); return 0;
	}
	factorial(); //팩토리얼 한번에 구해놓기
	
	//페르마의 소정리로 { (n!%MOD) * (k!*(n-k)!)^MOD-2 % MOD } % MOD

	ll A = fac[n] % MOD; 
	ll B = (power(fac[k], MOD - 2) % MOD * power(fac[n - k], MOD - 2) % MOD);
	printf("%lld", (A * B) % MOD);

	return 0;
}

주의해야 할 점은 

	ll B = (power(fac[k], MOD - 2) % MOD * power(fac[n - k], MOD - 2) % MOD);

이 식에서 각각의 fac[k]*fac[n-k]의 식으로 해주면 오버플로가 발생하는 것 같다.

그래서 따로 처리해줬더니 맞았다.