이항 계수 3 (feat. 백준, 11401번)

이항 계수 3
https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
long long factorial(long long N) {
	long long f = 1;
	while (N)
		f = f * (N--) % 1000000007;
	return f;
}
long long my_pow(long long base, long long expo) {
	if (expo == 1)
		return base % 1000000007;
	long long tmp = my_pow(base, expo / 2);
	if (expo & 1)
		return (tmp * tmp % 1000000007) * base % 1000000007;
	return tmp * tmp % 1000000007;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, K;
	cin >> N >> K;
	register long long t1 = factorial(N);
	register long long t2 = factorial(K) * factorial(N - K) % 1000000007;
	cout << t1 * my_pow(t2, 1000000007 - 2) % 1000000007;
	return 0;
}
// *&)*@*

페르마의 소정리를 이용하여 아래의 식에 대입합니다.

페르마의 소정리는 아래의 링크를 참고하세요.

페르마의 소정리 - 위키백과, 우리 모두의 백과사전