[BOJ 13977, Python 3] 이항 계수와 쿼리
https://www.acmicpc.net/problem/13977
13977번: 이항 계수와 쿼리
\(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
www.acmicpc.net
참조
다양한 방법의 이항계수 알고리즘 : https://koosaga.com/63
이항계수 (nCr) mod p 계산하기
nCr = n! / (n-r)! * r! 일 때, nCr mod prime을 빠르게 계산하는 방법에 대해서 얘기하려 한다. nCr 한 쿼리는 O(1)에 처리되어야 한다고 가정한다. (즉 전처리 한번 한 이후 nCr을 하나 계산하는데 O(1)) 1. O(n..
koosaga.com
페르마의 소정리 증명 : https://youtu.be/uhXOkoXtULI
$O(nlogp)$가 걸리는 이항계수 알고리즘 : https://velog.io/@gidskql6671/%EC%9D%B4%ED%95%AD-%EA%B3%84%EC%88%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98-%EC%86%8C%EC%A0%95%EB%A6%AC
이항 계수 알고리즘 - Dynamic Programming, 페르마의 소정리
이항 계수 알고리즘을 구현하자. Dynamic Programming을 통한 구현과 페르마의 소정리를 이용한 구현...
velog.io
풀이
페르마의 소정리와 빠른 거듭제곱 알고리즘을 사용하여 $O(nlogp))$ 시간이 걸리는 이항계수 알고리즘을 사용하면 됩니다.
주의할 점은 팩토리얼 값을 미리 계산해둬야 시간 초과를 피할 수 있습니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
input = __import__('sys').stdin.readline
MOD = int(1e9 + 7)
N = 4 * int(1e6) + 1
factorial = [1] * N
for i in range(1, N):
factorial[i] = (factorial[i-1] * i) % MOD
for _ in range(int(input())):
n, k = map(int, input().split())
A = factorial[n]
B = (factorial[k] * factorial[n - k]) % MOD
B2 = 1
expo = MOD - 2
while expo:
if expo % 2: B2 = (B * B2) % MOD
B = (B * B) % MOD
expo //= 2
res = (A * B2) % MOD
print(res)
|
cs |