[BOJ] 11401 : 이항 계수 3 - travelbeeee

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

---

[ 알고리즘풀이 ]

나누는 수 1,000,000,007 이 소수이므로 페르마 소정리와 고속 지수화 연산을 이용하면 된다.

( 고속 거듭제곱 연산 : https://travelbeeee.tistory.com/117?category=800452 )

#include<iostream>
#define P 1000000007

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	long long N, K, A = 1, B = 1, C = 1;
	cin >> N >> K;
	for (int i = 1; i <= N; i++)
		A = (A * i) % P;
	for (int i = 1; i <= N - K; i++)
		B = (B * i) % P;
	for (int i = 1; i <= K; i++)
		C = (C * i) % P;
	
	long long ex = P - 2, mulB = B,mulC = C, ansB = 1, ansC = 1;
	while (ex) {
		if (ex % 2 == 1)
			ansB = (ansB * mulB) % P;
		mulB = (mulB * mulB) % P;
		ex /= 2;
	}

	ex = P - 2;
	while (ex) {
		if (ex % 2 == 1)
			ansC = (ansC * mulC) % P;
		mulC = (mulC * mulC) % P;
		ex /= 2;
	}

	cout << (((A * ansB) % P)* ansC) % P;
}

---