11401번 이항계수 3

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

Keywords: Fermat's little theorem, Modular arithmetic

사실 이 문제는 이항계수를 묻는 문제라기 보다는 modular arithmetic 을 잘 알고 있는지를 묻는 문제이다. modular arithmetic 이라하면, 대표적으로는 아래 3개를 예시할 수 있다.

\[\begin{align*} (a (mod\ X) + b (mod\ X)) mod\ X & = (a + b) mod\ X \\ (a (mod\ X) - b (mod\ X)) mod\ X & = (a - b) mod\ X \\ (a (mod\ X) * b (mod\ X)) mod\ X & = (a * b) mod\ X \\ \end{align*}\]

그럼 여기서, “어?! 사칙연산인데, 나누기는 빠졌네?” 라는 생각이 드는 것이 인지상정이리라. 결론부터 말하면 나누기 연산에 대해서는 위와 같은 성질 (i.e. 각각 modular 하고 연산한 결과과 연산 결과를 modular 한 것이 같아지는) 이 만족되지 않는다. 그런데, \(X\)가 소수라는 가정이 있다면 그나마 Fermat’s little theorem 를 응용하여 유용한 성질 하나를 이끌어 낼 수 있다.

Fermat’s little theorem

Prime number \(p\) 와 정수 \(n\) 에 대해서 \(n^p \equiv n\ (mod\ p)\) 가 성립한다.

당신이, \(\frac{a}{b} (mod\ p)\) 를 구하고 있다고 가정해보자 (\(p\) 는 소수). 그렇다면, 아래가 성립한다.

\[\begin{align*} \frac{a}{b} (mod\ p) & = ab^{-1} (mod\ p) \\ ab^{-1} (mod\ p) & = ab^{p-2} (mod\ p)\ (\because n^p \equiv n\ (mod\ p) \Rightarrow n^{p-2} \equiv \frac{1}{n} (mod\ p)) \\ \end{align*}\]

그래서, 이 새키 뭐 자꾸 딴소리야 싶은 사람들도 있으리라. 이 문제에 위에서 언급한 내용은 아래와 같이 적용이 된다. 여기서, “미친놈이 그럼 \(N!((N-K)!K!)^{P-2}\) 는 직접 구하라는거야 뭐야?” 같은 의문이 들 수 있다. 이것은 분할정복을 통해서 잘 구해주도록 하자.

\[\frac{N!}{(N-K)!K!} (mod\ P) = N!((N-K)!K!)^{P-2} (mod\ P)\]

아래는 솔루션이다.

#include <cstdint>
#include <iostream>
#include <tuple>

constexpr std::int64_t P{1000000007};
std::int64_t N;
std::int64_t K;

std::tuple<std::int64_t, std::int64_t> GetNumDenom(std::int64_t n,
                                                   std::int64_t k) {
  std::int64_t numerator{1};
  for (int i{1}; i <= n; ++i) {
    numerator *= i;
    numerator %= P;
  }
  std::int64_t denominator{1};
  for (int i{1}; i <= k; ++i) {
    denominator *= i;
    denominator %= P;
  }
  for (int i{1}; i <= n - k; ++i) {
    denominator *= i;
    denominator %= P;
  }
  return {numerator, denominator};
}

std::int64_t GetPow(int base, int exponent) {
  if (exponent == 0) {
    return 1;
  } else {
    auto half{GetPow(base, exponent / 2) % P};
    auto half_sq{(half * half) % P};
    return exponent % 2 == 0 ? half_sq : (half_sq * base) % P;
  }
}

std::int64_t Solve() {
  auto [numerator, denominator] = GetNumDenom(N, K);
  return (numerator * GetPow(denominator, P - 2)) % P;
}

int main(void) {
  // For faster IO.
  std::ios_base::sync_with_stdio(false);
  std::cout.tie(nullptr);
  std::cin.tie(nullptr);

  // Read inputs.
  std::cin >> N >> K;

  // Solve.
  std::cout << Solve() << std::endl;

  return 0;
}