[백준][파이썬]11401번 - 이항 계수 3

문제

자연수 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로 나눈 나머지를 출력한다.

---

필요한 개념 및 알고리즘

dp

https://velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP

[자료구조와 알고리즘] 동적 계획법(Dynamic Programming, DP)

 

분할정복

https://janghw.tistory.com/entry/알고리즘-Divide-and-Conquer-분할정복

[알고리즘] Divide and Conquer (분할정복)

 

모듈러 연산

 

 

파르마의 소정리

https://youtu.be/RLVW9XrvjhM

 

 

풀이

이항 계수 공식

N의 최대 입력 값이 매우 크기때문에 조건에 따라 1,000,000,007로 나눠줘야 한다.

이를 p로 두자.

모듈러 연산은 분수꼴에 적용할 수 없기때문에 곱셈꼴로 변경해주어야 한다.

 

이에 페르마의 소정리가 사용된다.

위의 식을 계산하기 위해 k!(n-k)! % p의 역원을 구해야 한다.

p가 소수이고 a가 p의 배수가 아니면

위 공식이 성립한다.

이를 변형하면

즉, (k!(n-k)!)-1 % p = (k!(n-k)!)p-2  % p 가 된다.

 

# 페르마의 소정리 이용

# 분할 정복을 이용하여 a^b를 구한다.
def power(a, b):
    if b == 0:
        return 1
    if b % 2:  # 홀수이면
        return (power(a, b // 2) ** 2 * a) % p
    else:
        return (power(a, b // 2) ** 2) % p


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

# nCk를 나타내기 위해 팩토리얼을 dp로 구해줍니다.
fact = [1 for _ in range(N + 1)]

for i in range(2, N + 1):
    fact[i] = fact[i - 1] * i % p

# A는 nCk의 분자가되고 B는 분모가 됩니다.
A = fact[N]
B = (fact[N - K] * fact[K]) % p

#여기서 페르마의 소정리가 사용됨
print((A % p) * (power(B, p - 2) % p) % p)

아직 코드가 다 이해되지 않아 더 고민하고 추가 포스팅을 할 예정이다.

 

 

 

출처

https://my-coding-notes.tistory.com/94

https://rhdtka21.tistory.com/123

https://kyun2da.github.io/2020/08/30/BinomialCoefficient/