본문 바로가기
문제 풀이/백준(BOJ)

[C++] 백준 11401번 : 이항 계수 3

by 희조당 2021. 7. 30.
728x90

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

 

11401번: 이항 계수 3

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

www.acmicpc.net


 문제 풀이

이전 정수론 단계에서 풀었던 문제의 확장 버전이다.

n과 k에 대해서 조합을 구하는 문제인데 n과 k의 범위가 400만이다.

오버플로우가 무조건 발생하기 때문에 1000000007로 나눈 나머지를 구해야 한다.

범위가 너무 크기 때문에 일반적인 방법으로 풀 수 없어 여기서 곱셈의 역원을 이용해야 한다.

 

곱셈의 역원은 을 만족하는 을 의미한다. 

나머지 연산 중 나눗셈에 대해서는 분배 법칙이 성립하지 않아 곱셈의 역원을 이용해 나눗셈을 곱셈으로 바꾸어 계산할 수 있다.

곱셈의 역원을 구하는 방법은 두 가지로 페르마의 소정리와 확장 유클리드 알고리즘이 있다.

그중 페르마의 소정리는 나누는 값 m이 소수여야 하고 나누는 대상 a와 서로소야 한다.

위의 조건들을 만족하기 때문에 페르마의 소정리를 이용해 값을 구할 수 있다.

N! / (N - K)! K! 에서 A = N!, B = (N - K)! K!로 두면 A/B (mod M) 으로 볼 수 있다.

페르마의 소정리를 이용하면 을 구하면 된다!

여기서 B의 m-2 제곱을 구하기 위해서 단순히 반복문을 사용하면 20초 이상의 시간이 걸리기 때문에

앞서 공부했던 분할 정복을 이용해서 구하면 된다.

주의할 점은 값이 크기 때문에 오버플로우가 발생할 수 있어 중간중간에 계속 모듈러 연산을 해주어야 한다.

 느낀 점

나는 컴공인데.. 왜 페르마의 소정리까지 이해해가면서 수학 문제를 푸는지 약간 당황스러운 문제였다. 메모리 측면에서 오버플로우가 뜨지 않도록 신경 쓰는 법을 공부했다고 생각하려고 한다. 상당한 난이도가 있던 문제였다.

 코드

#include <iostream>

using namespace std;

int n, k;
long long mod = 1000000007;
long long n1 = 1, n2 = 1;

long long pow(long long n, long long e) {
	if (e == 0) return 1;
	long long tmp = pow(n, e / 2) % mod;
	tmp = tmp * tmp % mod;
	if (e % 2 == 0) {
		return tmp % mod;
	}
	else {
		return n * tmp % mod;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;

	for (int i = n - k + 1;i <= n;i++) {
		n1 = n1 * i % mod;
	}
	for (int i = 1; i <= k;i++) {
		n2 = n2 * i % mod;
	}
	cout << n1 * pow(n2, mod - 2) % mod;
}

댓글