[C++] 11401번 이항 계수 3 - 수학, 정수론, 조합론, 분할 정복을 이용한 거듭제곱, 모듈로 곱셈 역원, 페르마의 소정리

1. 문제

• \(_{n}C_{k} \% 1,000,000,007\)을 구하시오

<입력>

• - 1 -   \(N, K(1 \leq N \leq 4,000,000, 0 \leq k \leq N)\)

<출력>

• \(_{n}C_{k} \% 1,000,000,007\)

2. 재정의

• X

3. 해결 방법

• \(P = N! \% M\)을 구하기
• \(S = (N-K)! \times k! \% M\) 구하기
• \(S^{1,000,000,005} \% M\) 구하기
• \(P \times S \% M\) 구하기

4. 실수한 점, 개선할 점

• nCr을 팩토리얼로 계산할 때 반복문 하나로 줄일 수 있다.

<코드>

#include <iostream>

using namespace std;
typedef long long ll;

// 소수
const int mod = 1000000007;

// <문제>
// nCk
int N, K;

// <Fermat's little theorem>
ll P=1, S=1;

void input() {
    cin >> N >> K;
    K = min(K, N-K);
}

ll DaC(ll a, int n) {
	ll ret;
	
	if (n == 0) return 1;
	if (n % 2) return (DaC(a, n - 1)*a) % mod;
	else
		ret = DaC(a, n / 2);

	return (ret * ret) % mod;
}

int solve() {
    for(int i=1; i<=K; i++) {
        P = P * (N-i+1) % mod;
        S = S * i % mod;
    }
    
    S = DaC(S, mod-2);
    
    return P*S%mod;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    cout << solve();
    
    return 0;
}

 

<페르마의 소정리(Fermat's litle theorem)>

https://m.blog.naver.com/hongjg3229/221650178981

[백준 11401] 이항 계수3 - 페르마의 소정리, modular inverse

 

<문제 바로가기>

https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.