11401 ์ดํ•ญ๊ณ„์ˆ˜ 3

์•Œ๊ณ ๋ฆฌ์ฆ˜(ํŽ˜๋ฅด๋งˆ์˜ ์†Œ์ •๋ฆฌ, ๊ฑฐ๋“ญ์ œ๊ณฑ)

1. ํŽ˜๋ฅด๋งˆ์˜ ์†Œ์ •๋ฆฌ ์ ์šฉ
	nCk = n! / k!(n-k)! % 1000000007 ์—์„œ A = n!, B = k!(n-k)!, p = 1000000007 ์ด๋ผ๊ณ  ํ•  ๋•Œ

	์œ„ ์‹์€ (A * B^(-1)) % p ๋ฅผ ์„ฑ๋ฆฝ
	ํŽ˜๋ฅด๋งˆ์˜ ์†Œ์ •๋ฆฌ๋Š” p๊ฐ€ ์†Œ์ˆ˜์ผ๋•Œ, p์™€ ์„œ๋กœ์†Œ์ธ a๊ฐ€ ์žˆ์œผ๋ฉด, a^p mod p = a mod p ๊ฐ€ ์„ฑ๋ฆฝ. -> a^p-1 mod p = 1 mod p ์ด๋ฏ€๋กœ a^p-1 mod p = 1 ์ด ์„ฑ๋ฆฝํ•จ์„ ์•Œ๋ ค์ฃผ๋Š” ๊ณต์‹
	์—ฌ๊ธฐ์„œ ์–‘๋ณ€์— a๋ฅผ ํ•œ๋ฒˆ ๋” ๋‚˜๋ˆ„๋ฉด
	a^p-2 mod p = a^(-1) ์ด ์„ฑ๋ฆฝํ•จ์„ ์•Œ ์ˆ˜ ์žˆ์Œ
	๋”ฐ๋ผ์„œ ์œ„ ์ดํ•ญ ๊ณ„์ˆ˜ ์‹์€ ๋‹ค์Œ์ฒ˜๋Ÿผ ๋ณ€ํ˜•๋œ๋‹ค.
	(A * B^(-1)) % p = (A * B^(p-2)) % p
2. A = n!๊ณผ B = k!(n-k)! ๋ฅผ ๊ตฌํ•œ ํ›„, ๊ฑฐ๋“ญ์ œ๊ณฑ ๊ณต์‹์œผ๋กœ B^(p-2)๋ฅผ ๊ตฌํ•˜๋ฉด ๋จ.


 A = n*...*(n-k+1), B = k! ๋กœ ๋‘๊ณ  ํ’€์–ด๋„ ๋จ
-> ์ฒ˜์Œ์— ํ‹€๋ ธ๋˜ ์ด์œ ๋Š” (k!)^(p-2)๊ฐ€ ์•„๋‹ˆ๋ผ (k)^(p-2)๋กœ ํ’€์—ˆ๊ธฐ ๋•Œ๋ฌธ

์ฝ”๋“œ

#include <iostream>
#define DIVIDE 1000000007
 
using namespace std;
 
long long getCoefficient(int n, int k);
long long getPower(long long n, long long k);
 
int main() {
	int n, k;
	cin >> n >> k;
	cout << getCoefficient(n, k) << endl;
 
}
 
long long getCoefficient(int n, int k) {
	if (k == 0 || k == n)
		return 1;
 
	long long top = 1, bottom = 1, bottom2 = 1;
 
	for (int i = n; i >= 1; i--)
		top = (top * i) % DIVIDE;
	top %= DIVIDE;ใ…
	for (int i = k; i >= 1; i--)
		bottom = (bottom * i) % DIVIDE;
	bottom %= DIVIDE;
	for (int i = n - k; i >= 1; i--)
		bottom2 = (bottom2 * i) % DIVIDE;
	bottom2 %= DIVIDE;
 
 
	bottom = (bottom * bottom2) % DIVIDE;
	top %= DIVIDE;
 
	return (top * (getPower(bottom, DIVIDE - 2))) % DIVIDE;
}
 
long long getPower(long long n, long long k) {
	long long result = 1, temp = n;
 
	while (k > 0) {
		if (k % 2 == 1) {
			result = (result * temp) % DIVIDE;
		}
		temp = (temp * temp) % DIVIDE;
		k /= 2;
	}
 
	return result % DIVIDE;
}