BOJ 11410: 이항 계수 3

작성일

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

  • 2월동안 187문제 풀기(지난달 누적 87개) (41/187)
  • 너무 쉬웠던 2630, 18258 생략
  • 나머지 연산의 역원이 $1/X = X^{M-2}$ 임을 이용하는 문제
  • 그리고 pow 함수 구현을 2진법 표현 이용해서 구하는 방식
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
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
int N, K;
const LL M = 1000000007;

inline LL mul(LL a, LL b) {
  return (a*b)%M;
}

inline LL add(LL a, LL b) {
  return (a+b)%M;
}

LL pow(LL a, LL e) {
  LL ans = 1;
  while(e) {
    if(e&1) ans = mul(ans, a);
    a = mul(a,a);
    e /= 2;
  }
  return ans;
}

int main() {
  cin >> N >> K;
  LL fact = 1, nF = 1, kF = 1, nkF = 1;
  for(int i = 1; i <= N; i++) {
    fact = mul(fact, i);
    if(i == N) nF = fact;
    if(i == K) kF = fact;
    if(i == N-K) nkF = fact;
  }
  LL bot = pow(mul(kF, nkF), M-2);
  cout << mul(nF, bot);
}