[BAEKJOON] 11401번 : 이항 계수 3

문 제

 

소 스  코 드

#include <iostream>

typedef long long INT;
constexpr INT P { 1'000'000'007 };

void Remain_Pow(const INT& , int , INT& );
void Binomial();


int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	
	Binomial();

	return 0;
}

void Remain_Pow(const INT& a, int b, INT& r) {
	INT temp{ a };
	while (0 != b) {
		if (b & 1) r = (r * temp) % P;
		temp = (temp * temp) % P;
		b >>= 1;
	}
}

void Binomial() {
	int N, K;
	std::cin >> N >> K;

	INT A{ 1 }, B{ 1 }, C{ 1 };

	if (N == K || 0 == K) {
		std::cout << "1 \n";
		return;
	}

	INT past_fac{ 1 }, next_fac;
	for (int i = 2; i <= N; ++i) {
		next_fac = (past_fac * i) % P;
		if (K == i)			B = next_fac;
		if ((N - K) == i)	C = next_fac;
		past_fac = next_fac;
	}
	A = next_fac;

	INT pow_B{ 1 }, pow_C{ 1 };
	Remain_Pow(B, P - 2, pow_B);
	Remain_Pow(C, P - 2, pow_C);

	INT result{ (((A * pow_B) % P) * pow_C) % P };
	std::cout << result << '\n';

}

 

풀 이

 

• [백준] 1629번 : 곱셈
• [위키백과] 페르마의 소정리
• 모듈러 연산

이항 계수 N과 K의 경우 

로 표현할 수 있다. 하지만 결과값을 1'000'000'007로 나머지 연산을 해야한다.

나눗셈에 대하여 모듈러 연산이 적용되지 않는다. 그러므로 분모에 있는 값의 역원을 구하여 곱해주어야 한다.
이때 사용되는 것이 페르마의 소정리이다.
$$a^{p} \equiv a (mod\;p)$$

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

위의 정의를 통하여, 
$$a^{p - 1} \equiv 1 (mod\;p)$$

$$B\;^{p-1} \equiv 1(mode \; p) \;\; \rightarrow \;\; B\times B\;^{p-2} \equiv 1 (mod\;p)$$

표현 할수 있고, B의 역원을 구할 수 있다.

그러므로 

$$A\times B\;^{p-2} \;mod \;1'000'000'007$$

$$(A\; mod \;1'000'000'007\times B\;^{p-2} \;mod \;1'000'000'007) \; mod\;\;1'000'000'007$$

라는 공식이 완성이 된다.

Factorial 공식을 통하여 N!, K!, ( N - K )! 를 구해야하는데 곱셈에 대하여 모듈러 연산이 성립하기 때문에, 누적값을 통하여 1 ~ N 까지에서 K와 N-K값을 구한 후,
$$((K!)^{p-2} \times (N-K!)^{p-2})\; mod \; 1'000'000'007$$

를 앞에 했던 곱셈 문제와 같이 풀어주면 된다.

 

출 력 값

 

 

문 제  출 처

문제 링크 : https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3