[파이썬 | BOJ | 11401] 이항 계수 3

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

11401번: 이항 계수 3

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수

 

를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)

 

출력

 

를 1,000,000,007로 나눈 나머지를 출력한다.

 

풀이

 

를 구하는 기본적인 다이나믹 프로그래밍 방법은 

 

로 정의되는 성질을 이용해서 푸는것이다.

 

하지만 이 문제에서 N의 제한이 매우크기 때문에 O(N^2)의 알고리즘으로는 시간초과가 걸리게된다.

 

이 문제를 해결하는 방법은

 

를 이용해서, 실제로 계산하는 것인데, 이 문제에서 1,000,000,007로 계속해서 나눠야 하는데, 분수꼴은 나머지 정리로 인해서 분자와 분모에다가 모두 나머지를 구해서 계산하게 되면 0으로 나누는 문제가 발생할 수 있기 때문에, 분수꼴을 곱셈꼴로 바꿔야 한다. 

 

이때 페르마의 소정리라는 것이 사용되는데, a^(p-1) ≡ 1 (mod p) 임을 이용해서

 

라고 표현할 수 있다.

 

이때 팩토리얼 계산을 미리 해놓는다고 하면, O(N + lgN) 으로 계산할 수 있다. (지수의 O(lgN) 알고리즘 사용)

따라서 시간내에 해결 할 수 있다.

 

지수의 O(lgN) 알고리즘은 이분 탐색을 이용한 방법을 사용하면 된다.

 

 

	# [파이썬 | BOJ | 11401] 이항 계수 3
	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
	# (A/B) % p
	# = A * B^-1 % p
	# = A * B^-1 * B^p-1 % p
	# = A * B^p-2 % p
	# = (A % p) * (B^p-2 % p) % p
	print((A % p) * (power(B, p-2) % p) % p )

view raw BOJ11401.py hosted with ❤ by GitHub