[BaekJoon] 이항계수, 페르마의 소정리, 거듭제곱 feat.11401번(이항계수3)

 + 이 글은 작성자가 직접 공부하고 복습하며 작성한 글입니다. 만약 직접 작성하지 않았다면, 꼭 출처를 밝히겠습니다!

 + 이 글은 개인적인 공부를 바탕으로 작성되었기에, 틀린 부분이 있을 수 있으며, 틀린 부분이 있다면 알려주시면 감사하겠습니다!

 + 이 글을 다른 곳으로 가져가신다면, 꼭 출처를 남겨주세요~

 + '참고사이트'는 공부하기 위해 참고한 사이트들을 모아 둔 것입니다.

 + 혹시라도 문제가 된다면 바로 조취를 취할테니, 말해주시면 감사하겠습니다!

 + 이번에도 많은 것을 배우게 해준 '이항계수3' 문제!

 + 해당 문제를 제대로 풀기 위해서는 배경 지식이 필요한데, 최소 '이항계수', '페르마의 소정리', '거듭제곱' 이렇게 3가지가 필요합니다.

 + 해당 문제를 풀기위해 간단히 정리하였으며, 보다 자세한 지식은 참고사이트를 확인해주세요~

---

[이항계수]

 + 이항계수란 n개의 원소에서 r개의 원소를 뽑아내는 경우의 수입니다.

 + 즉, 조합인 nCr을 구하는 것입니다.

 + nCr을 구하는 식은 n!/(r!(n-r)!) 입니다.

 + 이항계수와 관련된 법칙은 여러가지가 있지만, 가장 대표적으로 사용되는 법칙이 있습니다.

=> nCr = (n-1)Cr + (n-1)C(r-1)

 + 해당 법칙을 이용하지면, 작은 범위의 n에 한해서 문제를 풀 수 있습니다. 하.지.만. 11401문제를 풀기 위해서는 턱없이 부족합니다.

[페르마의 소정리]

 + 페르마의 소정리란, p가 소수이고 a가 정수일 때, 다음을 만족한다는 것입니다.

 

+ 위의 식의 뜻은, a^p를 p로 나눈 나머지가 a를 p로 나눈 나머지와 같다는 것입니다.

(a^p % p) = (a % p)

 + 여기서 끝이 아니라, 역수을 구해야 합니다. 역수이란, 특정 값 A에 대해서, A*X = 1이 나오게 하는 X를 말하는 것입니다.

 + 페르마의 소정리에서 양쪽에 a를 나눠주게되면

 + 위의 식을 발견하실 수 있으며, 양쪽에 a를 한 번 더 나눠 줌으로써, a의 역수가 a^(p-2) 임을 알게 되실 겁니다.

 + 이 식을 이항계수와 연관지으면, 아래의 식이 성립하게 됩니다.(문제의 %p를 대입)

nCr = n!/(r!(n-r)!) % p

-> A = n!, B = (r!(n-r)!)

-> (A*B^(-1)) % p

-> ((A % p)*(B^(-1) % p)) % p

-> B^(-1)은 B의 역수

-> (A*B^(p-2)) % p

 + 이로써, 분수가 아닌, 정수의 곱으로 이항계수를 표현할 수 있게 되었습니다.

 + 왜 정수로 표현해야하냐면, p로 나눠줘야 하는데, 분수는 나눠주기 힘들기 때문입니다.!

[거듭제곱]

 + p-2승 만급 거듭제곱을 해줘야 합니다.

 + 여러 방법이 있지만, 저는 2진수 표현법을 사용하였습니다.

 + 거듭제곱을 보면, A^2a = (A^a)^2 임을 알고 있으실 겁니다. 더 나아가, A^6a = (A^a)^6 = (A^a)^4 * (A^a)^2 = (A^a)^(2^2) * (A^a)^2 임을 알 수 있습니다.

 + 즉, 구하고자 하는 값을 2의 지수승의 합으로 나타낼 수 있습니다.

 + 그리고 이를 자세히보면, 지수를 2진법으로 나타낸 것과 같음을 발견할 수 있습니다.

a^14 = a^8 * a^4 * a^2

 + 이 것을 활용하여 거듭제곱을 구하게되면, O(logN)의 시간복잡도로 결과를 구할 수 있음을 알게 되실 겁니다!

*** 이해가 안되시면, 손으로 직접 적어가며 확인해보시면 됩니다~

*** 이해하는데 정말 시간 오래 걸렸다... 흑흑흑...

[코드]

 + 코드는 https://www.acmicpc.net/problem/11401의 문제풀이 과정을 참고하였습니다.

#include<iostream>
using namespace std;
 
#define FOR(x,y) for(int i = (x); i<(y); i++)
#define ll long long
#define DIV 1000000007
 
int N;
int K;
 
ll fact[4000002];
ll inv[4000002];
ll result;
 
// 분할 정복으로 구하는 제곱 수. 제곱수를 2진수로 생각해서, 2의 지수승 합으로 나타낼 수 있음을 응용한다.
ll power(ll value, ll index) {
    ll result = 1;
 
    while (index > 0)
    {
        if (index % 2 == 1) {
            result *= value;
            result %= DIV;
        }
 
        value *= value;
        value %= DIV;
        index /= 2;
    }
 
    return result;
}
 
int main() {
    cin >> N >> K;
    if(N == K || K == 0){
        cout << "1";
        return 0;
    }
    
    fact[1] = 1;
 
    // 여기서부터 구할 배열의 값들은, 미리 초기화를 시켜줘서, 접근 시간 복잡도를 1로 만들어 주기 위함이다.
    // factorial 초기화
    FOR(2, N + 1) {
        fact[i] = (fact[i - 1] * i)%DIV;
    }
 
    // 페르마의 소정리를 이용해서, a^(p-2)할 a를 설정해야하는데, 일단 그냥 N!으로 설정했습니다.
    inv[N] = power(fact[N], DIV - 2);
 
    // N!에 관한 역원값을 만들어 줬으니, (N-K)!을 위해, (N-1)!, (N-2)!을 미리 계산해준다.
    for (int i = N - 1; i > 0; i--) {
        inv[i] = (inv[i + 1] * (i + 1)) % DIV;
    }
 
    // N!/(K!(N-K)!) % DIV를 구해줍니다.
    // 주의해야할 점은 result *= value % DIV를 하면 안되고, 밑의 식처럼 풀어줘야 한다는 것입니다.
    result += fact[N];
    result = (result * inv[K])%DIV;
    result = (result * inv[N - K]) % DIV;
 
    cout << result;
 
    return 0;
}

---

** 참고사이트 **

<문제관련>

 - http://jason9319.tistory.com/169

 - http://koosaga.com/entry/%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%98-nCr-mod-p-%EA%B3%84%EC%82%B0%ED%95%98%EA%B8%B0

<이항정리>

 - https://namu.wiki/w/%EC%9D%B4%ED%95%AD%EC%A0%95%EB%A6%AC#rfn-3

 - http://makefortune2.tistory.com/109

<페르마의 소정리>

 - https://onsil-thegreenhouse.github.io/programming/problem/2018/04/02/problem_combination/

 - http://weeklyps.com/entry/%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98-%EC%86%8C%EC%A0%95%EB%A6%AC-%EC%9E%89%EC%97%AC%EC%97%AD%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0

 - http://freshrimpsushi.tistory.com/121

<거듭제곱>

 - http://return-true.tistory.com/1

Copyright © -강정이좋아- 무단 전재 및 재배포는 하지 말아주세요.