[백준] 15791 세진이의 미팅

문제는 남자 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시간만에 구하면 시간초과에서 피할 수 있다!

소스코드

#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);
}