[C/C++] 백준 11401번 - 이항 계수 3 (페르마 소정리, 분할정복)

 

 

 

<코드>

#include<iostream>
#include<cmath>
using namespace std;

long long N, K, A, B, half;
long long mod = 1000000007;

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

	if (x % 2 == 1) return B * solve(x - 1) % mod;
	else
	{
		half = solve(x / 2);
		return half * half % mod;
	}
}

int main()
{
	cin >> N >> K;
	A = 1;
	// A = N*(N-1)* .... *(N-K+1)
	for (int i = N; i >= N - K + 1; i--) A = (A * i) % mod;

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

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

	cout << A * B % mod;
	            
}

 

풀이방법

 

이항계수의 성질

모듈러(modulo)는 곱셈이나 덧셈에서 사용이 가능하지만 분수에는 적용하기가 곤란하여 A*B 형식으로 만들어 주어야 한다. 그에따라 필요한것이 페르마 소정리 인데,

페르마 소정리

즉, 페르마의 소정리에 의해 분모의 수를 아래와 같이 바꿀 수 있다.

 

그러므로 이항계수를 곱셈형식으로 만들어 줄 수 있게 되었고 곱셈은 모듈러 연산이 가능하기 때문에 

N*(N-1)*(N-2)ㆍㆍㆍ(N-K+1) 과 K! 을 구해주고

K!^(p-2) = K!^(mod-2)의 경우는 분할정복을 이용하여 구해준다. 

 

 

 

www.acmicpc.net/problem/11401

11401번: 이항 계수 3