[백준 13977] 이항 계수와 쿼리 (python)

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

13977번: 이항 계수와 쿼리

이항 계수와 쿼리 문제

이항 계수를 10**9+7로 나눈 나머지를 구하는 문제

모듈러 연산, 페르마의 소정리, 분할 정복에 대한 개념에 대한 이해가 있어야 풀 수 있던 문제

 

⚙️ 내가 푼 정답 코드

import sys
M = int(sys.stdin.readline())
p = 1000000007
factorial = [1]*4000001
for i in range(2,4000001): # 펙토리얼 구하기
    factorial[i] = (factorial[i-1]*i) % p
def find(x,n): # 제곱 구해주기
    if n == 1:
        return x % p
    else :
        temp = find(x,n//2)
        if n % 2 == 0:
            return temp*temp % p
        else:
            return temp*temp*x % p

for _ in range(M):
    N, R = map(int, sys.stdin.readline().split())
    print(factorial[N]*find(factorial[R]*(factorial[N-R]),p-2)%p) #이항계수 출력

📌문제 접근 포인트

1. 페르마의 소정리

 2. 위 (3)을 이용하여 이항 계수 변환

 

3. 위처럼 식을 변환했다면 이항 계수를 구하기 위해서 먼저 팩토리얼을 구해야 한다. 정해진 요구 조건이 N <= 4000000이므로 400만까지 펙토리얼을 DP 계산을 이용해서 먼저 구해주자.
4. 먼저 구해주는 형식이 아닌, 함수로 정의할 경우, M번의 테스트 케이스 동안 M번을 호출하게 되므로, 굉장히 시간이 오래 걸리게 된다.

5. 분할정복을 통해 제곱을 빠르게 계산처리 할 수 있도록 코드를 작성해주자.

6. 팩토리얼과 분할정복으로 구한 함수를 이용해서 위 2번의 식 그대로 작성해 주면 답을 어렵지 않게 구할 수 있다.