11401번 - 이항 계수 3

페르마의 소정리와 분할 정복을 이용한 거듭제곱을 이용한 풀이입니다.

#include <iostream>
#include <algorithm>
using namespace std;
int n, k;
int divider = 1'000'000'007;
long long int mul(long long int a, long long int b, long long int divider)
{
	long long int ans = 1;
	while (b > 0) {
		if (b % 2 != 0) {
			ans *= a;
			ans %= divider;
		}
		a *= a;
		a %= divider;
		b /= 2;
	}
	return ans;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> k;
	long long int a, b, b1, ans;
	a = 1;
	b = 1;
	for (long long int i = 1; i <= n; i++) {
		a *= i;
		a %= divider;
	}
	for (long long int i = 1; i <= k; i++) {
		b *= i;
		b %= divider;
	}
	for (long long int i = 1; i <= n - k; i++) {
		b *= i;
		b %= divider;
	}
	b1 = mul(b, divider - 2, divider);
	cout << (a * b1) % divider << endl;
	return 0;
}

 

https://en.wikipedia.org/wiki/Exponentiation_by_squaring

Exponentiation by squaring - Wikipedia