[Baekjoon] 11401번 : 이항 계수 3

1. 문제

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

• 분할정복 문제

// 문제
자연수 N과 정수 K가 주어졌을 때 이항 계수 
(N/K)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

// 입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)

// 출력
(N/K)를 1,000,000,007로 나눈 나머지를 출력한다.

// 예제 입력 1 
5 2

// 예제 출력 1 
10

2. 핵심 아이디어

• 페르마의 소정리를 이용하여 조합 공식 곱셈 형태로 변형

3. Python 문제풀이

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
num = 1000000007

def factorial(N) :
  n = 1
  for i in range(2, N+1) :
    n = (n * i) % num
  return n

def square(n, k) :
  if k == 0 :
    return 1
  elif k == 1 :
    return n
  tmp = square(n, k//2)
  if k % 2 :
    return tmp * tmp * n % num
  else :
    return tmp * tmp % num

top = factorial(N)
bottom = factorial(N-K) * factorial(K) % num

print(top * square(bottom, num-2) % num)

4. Java 문제풀이