백준 11401번(python)

---

# 거듭제곱을 빠르게 구하는 방법은 
# 백준 1629번을 참고하세요.
def solve(A, B):
    if(B % 2 > 0):
        return solve(A, B - 1) * A
    elif(B == 0):
        return 1
    elif(B == 1):
        return A
    else:
        result = solve(A, B//2)
        return result ** 2 % p

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

n_part = 1
nk_part = 1

p =  1000000007

# N! 부분
for num in range(1, N+1):
    n_part *= num; n_part %= p

# K! 부분
for num in range(1, K+1):
    nk_part *= num; nk_part %= p

# (N-K)! 부분
for num in range(1, N-K+1):
    nk_part *= num; nk_part %= p
    
# (p-2) 제곱 부분은 거듭제곱을 빠르게 구하는 방법을
# 그대로 가져와서 사용합니다.
nk_part = solve(nk_part, p-2) % p

result = (n_part * nk_part) % p
print(result)

페르마의 정리를 처음 접해봤는데, 무엇보다 이항계수가 페르마의 정리에 의해 어떻게 단순화될 수 있는지 직접 손으로 풀어보면 바로 코드로 옮길 수 있을 것이다.

페르마의 정리를 통해 이항계수의 분모에 해당하는 K!(N-K)!를 거듭제곱 형태로 바꿔주어 시간복잡도를 줄일 수 있다.