백준 - 11401번(재귀,이항계수, 페르마 소정리)

이항 계수가 뭔지 기억이 안 나서 이것부터 찾아봤다.

이것이 이항정리

페르마의 소정리 라는 공식을 사용하면 코딩에 용이한 식으로 바꾸는 것이 가능하다.

또한 함수로 팩토리얼 계산을 미리 해놓으면 시간 복잡도를 O(N+logN) 정도로 개선 가능하다/

페르마의 소정리

import sys
read = sys.stdin.readline

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, read().split())

fact = [1 for _ in range(N+1)]

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

A = fact[N]
B = (fact[N-K] * fact[K]) % p

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