티스토리 뷰
문제는 남자 n명 , 여자 m명 (n>=m) 일 때 nCm % mod를 구하는 문제다
nCm = n! / m!(n-m)! 인데 여기서 바로 %mod를 해버리면 답이 안나온다
우리는 페르마의 소정리를 사용해서 문제를 풀어야 한다!
페르마의 소정리
==> p가 소수이고 a와 p가 서로소 일 때 a^p=a(mod p) 가 성립한다
a*a'=1(mod p) 일때 a'가 역원이라고 하자
이 때 페르마의 소정리에 의해 a^(p-1) = 1(mod p) 가 성립한다
그럼 a*a^(p-2) =1(mod p)가 되므로 역은 a^(p-2)다!!
그럼 a/b = a/b*b*b' = a*b' = a*b^(p-2) 가된다~!
b^(p-2)는 log시간만에 구하면 시간초과에서 피할 수 있다!
소스코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include <iostream> using namespace std; #define ll long long ll mod = 1e9 + 7,n,m; ll a = 1, b = 1, c = 1; ll mypow(ll a, ll b) { if (!b) return 1; if (b & 1) return (a*mypow(a, b - 1)%mod) % mod; return mypow((a*a) % mod, b / 2) % mod; } int main() { scanf(" %lld %lld", &n, &m); for (ll i = 1; i <= n; i++) { a *= i; a %= mod; } for (ll i = 1; i <= m; i++) { b *= i; b %= mod; } for (ll i = 1; i <= n - m; i++) { b *= i; b %= mod; } c = mypow(b, mod - 2); a *= c; a %= mod; printf("%lld\n", a); } | cs |
댓글