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

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

11401번: 이항 계수 3

1. 코드 설명

• 이항 계수를 구하는 공식이다. 범위가 4,000,000이라서 일반적인 공식으로는 풀기 불가능
• 페르마의 소정리를 활용한 코드, 확장 유클리드 호제법의 두가지 방식으로 풀 수 있다.
• 페르마의 소정리 - p가 소수이고 a가 p의 배수가 아니면 a^(p-1)의 p로 나눈 나머지는 1이다.
• 유클리드 호제법 - 자연수 a,b가 주어졌을 때, a와 b의 최대 공약수를 구하는 방법. - gcd(a,b)
• 확장 유클리드 호제법 - 정수해를 갖는 부정 방정식 ax+by=c 이 주어질 때, 이 방정식을 만족하는 (x,y)값을 구할 수 있다. 

2. 예

3. 코드

# 분할 정복을 이용하여 a^b를 구한다.
def fermat(a, b):
    if b == 0:
        return 1
    if b % 2:
        return (fermat(a, b//2) ** 2 * a) % p
    else:
        return (fermat(a, b //2) ** 2) % p
    
p = 1000000007
n, k = map(int, input().split())

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

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

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

print((A % p) * (fermat(B, p - 2) % p) % p)