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 1000000007using 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;}