[BOJ] 11401번 이항 계수 3

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

풀이시간: 첫 풀이 실패후, 성공 제출까지 1시간 40분

파스칼 법칙을 이용해서 +에서의 모듈로 연산 분배법칙으로 DP로 접근하려 했지만 그렇게 되면 $O(N*K)$로 시간초과가 발생한다.

모듈로 연산의 나눗셈을 처리하는 법(페르마의 소정리 이용)을 알아야 하고, 제곱 수를 빠르게 구하는 방법까지 알아야 풀 수 있는 문제이다.

모듈로 연산

/을 제외한 +,-,X에서 모두 분배법칙을 이용할 수 있다.

이때 /에서 분배법칙은 특수한 경우에 가능하다.

(출처: https://goodteacher.tistory.com/398)

문제에서 주어진 P=1,000,000,007는 소수이고, N이 최대 4,000,000까지이므로 /의 분배법칙을 적용할 수 있다.

제곱 수를 빠르게 구하는 법

관련문제: https://www.acmicpc.net/problem/1629
풀이: https://velog.io/@hozero/BOJ-1629%EB%B2%88-%EA%B3%B1%EC%85%88

주어진 식 정리 & 풀이

위의 두 정보를 통해 문제의 식을 정리해보면 다음과 같아진다.

1. DP를 통해 4,000,000까지 N!modM을 구해두고,
2. 1에서 구한 값을 가지고 제곱 수를 빠르게 구하면 된다.

def pow_plus_modulo(num, n, m):  # (num^n) % m 구하기
    if n == 1:
        return num % m

    if n % 2 == 0:  # n이 짝수
        return (pow_plus_modulo(num, n // 2, m)**2) % m
    else:
        return ((pow_plus_modulo(num, (n - 1) // 2, m)**2) * (num % m)) % m


M = 1000000007

# dp[N] = N!modM
dp = [1]
for i in range(1, 4000001):
    dp.append((dp[i - 1] * i) % M)

N, K = map(int, input().split())
ans = (dp[N] * pow_plus_modulo(dp[K] * dp[N - K], M - 2, M) % M) % M
print(ans)

스터디: dp 따로 저장 안해놔도 될 듯 O(N)이니까