[백준 11401] 이항 계수 3 (C++)

문제 링크: https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

1. 주의할 점

- 계산을 진행할 때 마다 MOD연산을 해줘야한다

- TLE를 막기 위해 Pow함수를 직접 구현해줘야 한다

- 페르마의 소정리에 대해 알고 있어야 한다.

 

2. 구현

- 페르마의 소정리를 이용한다

Ex) (A!/B!) % MOD ->(A! * Pow(B,MOD-2)) % MOD로 바뀐다

- Pow 함수는 분할정복을 이용해서 해결한다. Idx가 0과 1일 때를 제외하곤 Idx가 짝수면 {Pow(Num, Idx/2)* Pow(Num, Idx/2)} % MOD를 반환하고 Idx가 홀수면 {(Pow(Num,Idx-1)*Num)} % MOD를 반환한다

 

#include <iostream>
using namespace std;
long long MOD = 1000000007;
int n, k;

long long pow(long long num, long long idx) {
	if (idx == 0) return 1;
	else if (idx == 1) return num;
	if (idx % 2 == 0) {
		long long temp = pow(num,idx/2) % MOD;
		return (temp*temp) % MOD;
	}
	long long temp = pow(num, idx - 1) % MOD;
	return (num*temp) % MOD;
}

int main() {
	cin >> n >> k;
	long long up = 1, down = 1, result;
	for (int i = 2; i <= n; i++) {
		up *= i;
		up %= MOD;
	}
	for (int i = 1; i <= n - k; i++) {
		down *= i;
		down %= MOD;
	}
	for (int i = 1; i <= k; i++) {
		down *= i;
		down %= MOD;
	}
	result = up*pow(down, MOD - 2);
	cout << result % MOD;
	system("pause");
	return 0;
}