티스토리 뷰


문제는 남자 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 & 1return (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


댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2025/07   »
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
글 보관함