[Baekjoon/백준] 11401번: 이항 계수 3(C/C++)

단계별로 풀어보기 20단계(분할 정복) 5번 문제

https://www.acmicpc.net/step/20

분할 정복 단계

---

백준 11401번: 이항 계수 3

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

11401번: 이항 계수 3

---

문제 설명

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

---

입력과 출력

입력: 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)

출력: nCk를 1,000,000,007로 나눈 나머지를 출력한다.

---

접근 방법

이번 문제는 N과 K를 입력받아서 이항계수 nCk를 1,000,000,007로 나눈 나머지를 출력하는 문제다.

역시 수학에서 손 땐지 너무 오래되서 그런지 수학 문제는 너무 어렵다.. 예전에 풀어봤던 이항 계수 1, 2 문제들을 보면서 이를 기반으로 고민을 많이 해봤는데 잘 되지 않았다. 그래서 인터넷을 찾아서 이 블로그 글과 이 블로그 글을 참고해서 해결했다.

이항 계수 정의

이항 계수 2 풀이에 사용했던 점화식

우선 이항 계수는 위 식들처럼 계산할 수 있다. 이는 예전에 풀어봤던 문제들로 인지하고 있었다. 다만 이항 계수 2번 문제처럼 진행할 경우 10억이 넘는 숫자를 계산해야해서 시간초과가 발생할 것이다. 그리고 정의를 사용하더라도 분수에서 나머지 연산을 하는 것은 분모가 0이 될 수 있으므로 불가능하다.

페르마의 소정리

요약

그래서 다른 방법을 찾아야한다. 여기서 '페르마의 소정리'를 활용한다. 이를 분모에 적용하면 아래 식과 같이 나오게 된다. 이를 활용해서 분할 정복을 하면서 문제를 풀면 된다.

이항 계수 분모 변환 식

적용한 식

---

코드

#include <iostream>
using namespace std;

long long int A = 1, B = 1;

long long int solve(long long int X) {
	if (X == 0)	return 1;

	if (X % 2 == 1)
		return B * solve(X - 1) % 1000000007;

	long long int temp = solve(X / 2);
	return (temp * temp) % 1000000007;
}

int main(int argc, char *argv[]) {
	long long int N, K;
	cin >> N >> K;
	
	for (int i = N; i >= N - K + 1; i--)	//N * (N - 1) * ... *(N - K + 1)
		A = (A * i) % 1000000007;

	for (int i = 1; i <= K; i++)	//K!
		B = (B * i) % 1000000007;

	B = solve(1000000007 - 2);	//K!^(p - 2)

	cout << A * B % 1000000007 << endl;

	return 0;
}

---

결과

백준 제출 결과