2/BOJ
백준 11401번 - 이항계수3
하례은
2020. 10. 13. 20:18
11401번: 이항 계수 3
자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
www.acmicpc.net
처음엔 평범하게 풀었다가 왜 안되나 봤더니 n의 크기가 4,000,000 이하라 유클리드 호제법/ 페르마의 소정리 둘 중 하나로 풀어야 되는 문제였다. 물론 다른 방법도 있지만...검색으로 페르마의 소정리법을 배웠다...
이항계수의 식을 풀어 페르마의 소정리에 적용시킨것.
도움받은 블로그는 onsil-thegreenhouse.github.io/programming/problem/2018/04/02/problem_combination/
#분할 정복을 이용
def bine(a,b):
if b == 0:
return 1
if b % 2:
return (bine(a,b//2)**2 * a)%p
else:
return (bine(a,b//2) ** 2)%p
n,k = map(int,input().split())
p = 1000000007
# 펙토리얼을 구하기 위해 dp사용
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) * (bine(B,p-2)%p)%p)
구글 검색의 힘을 빌려 풀었다....ㅎ...펙토리얼도 for문으로 구했다가 시간초과로 사용불가능이였고 분할 정복을 이용해 a^b를 구해 시간을 절약하는 것도 배웠다릐
넘넘넘 어려운 문제였다 ㅠㅠ 모자른 나는 오늘도 한단계 성장~ㅎㅎ