기타. [11401]

[1. 문제 설명]

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

---

[2. 풀이 접근]

페르마 소정리를 이용하여, 모듈러 연산의 분배 법칙을 유도해야 한다.

 

여기서 p 는 1,000,000,007 로 이 값은 소수이다.

• 이 값이 소수임이 문제에 있진 않지만.,,
• z 와 p 가 서로소가 될 수 있나?

---

[3. 코드]

	#include <iostream>
	#include <algorithm>
	using Int = long long;
	const Int MOD = 1e9+7;
	Int factorial(const int n)
	{
	if (n == 0) {
	return 1;
	}
	Int result = n;
	for (int j = n-1; j > 1; j--) {
	result *= j;
	result %= MOD;
	}
	return result;
	}
	Int power(const int v, const int n)
	{
	if (n == 0) {
	return 1;
	}
	if (n == 1) {
	return v;
	}
	Int result = 0;
	if (n % 2 == 0) {
	result = power(v, n/2) % MOD;
	result *= result;
	} else {
	result = v * power(v, n-1);
	}
	return result % MOD;
	}
	Int solve(const int N, const int K)
	{
	const Int n_f = factorial(N) % MOD;
	const Int k_nk_f = (factorial(K) * factorial(N-K)) % MOD;
	const Int k_nk_f_mod = power(k_nk_f, MOD-2) % MOD;
	return (n_f * k_nk_f_mod) % MOD;
	}
	int main()
	{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int N, K;
	std::cin >> N >> K;
	const Int result = solve(N, K);
	std::cout << result << "\n";
	return 0;
	}

view raw 11401.cpp hosted with ❤ by GitHub