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

설명

일단 이 문제를 풀기 위해선 페르마의 소정리와 모듈러 역원을 구하는 연산을 할줄 알아야한다.

소스코드

#include<iostream>
using namespace std;

int n, r;
int fact[4000001];
const long long MOD = 1000000007;

long long getFact(long long n) {
	if (n == 0) return 1;
	if (fact[n]) return fact[n];
	return fact[n] = n * (long long)getFact(n - 1) % MOD;
}

long long power(long long base, int exp) {
	if (!exp) return 1;
	long long i = 1;
	while (exp) {
		if (exp % 2) {
			i *= base;
			i %= MOD;
			exp--;
			continue;
		}
		base *= base;
		base %= MOD;
		exp /= 2;
	}
	return i;
}

int main() {
	cin >> n >> r;
	long long numer = getFact(n);
	long long deno = getFact(r) * getFact(n - r) % MOD;
	deno = power(deno, MOD - 2);
	numer = numer * deno % MOD;
	cout << numer;
}