백준 11401 이항 계수 3(파이썬)
접근방식
- 처음에는 combination식에서 중복되는 연산을 찾아 분할을 하려했지만 도저히 방도를 못찾겠어 구글링을 해보니
페르마의 소정리또는유클리드 호제법을 사용하여 푸는 문제라는 것을 알았다. - 대부분 페르마의 소정리를 사용하여 푸셨는데 아마 더 빠르고 간편해서 인 것 같다.
- 페르마의 소정리가 뭐인고 하니 p가 소수이고 a가 정수일 때 a^p = a (mod p)이다. 즉 a^(p-1)을 p로 나눈 나머지는 1이다.
- 앞서 내용은 참고에 달아둔 블로그에 큰 도움을 받았다!
파이썬 코드
import sys
div = 1000000007
n, k = map(int,sys.stdin.readline().split())
# 분할 정복을 이용한 a^b
def power(a,b):
if b == 0:
return 1
if b % 2:
return (power(a, b // 2) ** 2 * a) % div
else:
return (power(a, b // 2) ** 2) % div
# 팩토리얼 구하기
fact = [1 for _ in range(n+1)]
for i in range(2,n+1):
fact[i] = fact[i-1] * i % div
# 분모
denominator = (fact[n-k] * fact[k]) % div
# 분자
numerator = fact[n]
# 페르마 소정리
print((numerator % div) * (power(denominator, div - 2) % div) % div)
참고
https://kyun2da.github.io/2020/08/30/BinomialCoefficient/
https://www.acmicpc.net/board/view/15795
