[백준][C++] 11401: 이항 계수 3

 

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

11401번: 이항 계수 3

 

 

 

 

---

- 문제

 

  자연수 N과 정수 K가 주어졌을 때 이항 계수 NK를 1,000,000,007로 나눈 나머지를 구하는 문제다.

 

 

---

- 해설

 

진짜 이거는 외워놓지 않으면 직접 생각하는건 힘든 문제일 것이다.

 

위는 기본이고,

 

 

 

A와 B로 치환을 하게 되면 위와 같이 바뀐다.

 

그리고 이제 

 

페르마의 소정리는 아래와 같은데, 

 

 

mod p는 p로 나눈 나머지라고 생각하면 된다. 그럼 이걸 A와 B로 치환한 거에 넣어보면

 

A/B에서 1/B를 위와 같이 바꿔줄 수 있다.

 

결국 

 

A/B를 1,000,000,007로 나누어야 하기 때문에 1,000,000,007을 MOD라고 하면 

 

 

위 식이 나오고, 이걸 정리하면 

 

 

위의 식이 만들어진다.

 

 

밑에 풀이에서 solve(mod - 2)를 하는 이유가 위의 식에서 나온다. B에 p-2제곱을 하는 것이다.

 

이후에 A * B % mod를 하면 이게 위의 식과 같게 된다.

 

 

---

- 풀이

#include <iostream>
using namespace std;

long long N, K, A, B, half;
long long mod = 1000000007;

long long solve(int x)
{
    if (x == 0)
    {
        return 1;
    }
    if (x % 2 == 1)
    {
        return B * solve(x - 1) % mod;
    }
    else
    {
        half = solve(x / 2);
        return half * half % mod;
    }
}

int main()
{
    cin >> N >> K;
    A = 1;
    // A = N*(N-1)* .... *(N-K+1)
    for (int i = N; i >= N - K + 1; i--)
    {
        A = (A * i) % mod;
    }

    // B = K!
    B = 1;
    for (int i = 1; i <= K; i++)
    {
        B = (B * i) % mod;
    }

    // B = (K!)^(p-2)
    B = solve(mod - 2);

    cout << A * B % mod;

    return 0;
}

 

 

---

- 새롭게 알게 된 점

- 페르마의 소정리

- 이항계수

- 분할정복 함수, 공식, 원