11401_이항계수3

문제는 더보기!

 

이항 계수 3

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

15607

5866

4224

42.109%

문제

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

입력

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

출력

 (NK)\(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1 복사

5 2

예제 출력 1 복사

10

 

 

문제는 간단해 보이지만.. 그렇지 않다. 

 

이전에 이항계수를 풀어본 적과 곱셈을 해본푼 적이 있다.

 

특히 이항계수를 풀기 위해서는 팩토리얼이 들어가기때문에 미리 리스트를 만드는 식을 통해 구현했었다.

 

이렇게 풀면 메모리 초과가 나게된다. 그래서 페르마의 소정리를 이용해서 구하면 된다.

import sys
n,k = map(int,sys.stdin.readline().split())
num = 1000000007

def f(a,b):
    if b ==1:
        return a%num
    d = f(a,b//2)
    if b%2 ==0:
        return d * d%num
    else:
        return d * d*a%num



fac = [ 1 for _ in range(n+1)]

for i in range(2,n+1):
    fac[i] = fac[i-1] * i % num



a = fac[n]
b = fac[n-k] * fac[k] % num

print((a % num) * (f(b,num-2) % num)%num)