[SWEA / PYTHON] 5607.[Professional] 조합

import os
import sys


current_file = os.path.basename(__file__)[:-3]
sys.stdin = open(f"input/{current_file}_input.txt", "r")


result = []

T = int(input())

def fp(N, p):
    global C
    if p == 0:
        return 1

    half = fp(N, p // 2)

    if p % 2 == 0:
        return (half % C) ** 2 % C
    else:
        return (((half * N) % C) * (half % C)) % C


C = 1234567891

fac = [1] * 1000001

for i in range(1, 1000001):
    fac[i] = (fac[i - 1] * i) % C

for case in range(1, T + 1):
    N, R = map(int, input().split())

    # [ (N! % C) / { ((N-R)! % C) * (R! % C) } ] % C
    # => [ (N! %C) * { ((N-R)! % C) * (R! % C) }** (C-2) ] % C

    top = fac[N] % C
    bottom = (fac[N - R] % C) * (fac[R] % C)
    bottom_reversed = fp(bottom, C - 2)

    ans = top * bottom_reversed % C

    result.append(f"#{case} {ans}")

for _ in result:
    print(_)


output = open(f"input/{current_file}_output.txt", "r").readlines()
output = [line.strip() for line in output]

print("------------------- 오답 ------------------ ( 이 아래로 출력이 없으면 정답)")

for r, o in zip(result, output):
    if r != o:
        print(f"정답 : {o},     오답 : {r}")

풀이.

우선 이 문제를 풀려면 페르마의 소정리, 거듭제곱의 분할정복 방법을 알아야지만 풀 수 있다.
무작정 조합 하려한다면 시간 초과가 10,000% 발생한다.
그리고, 페르마의 소정리를 이용한다고 하더라도, 그냥 거듭제곱을 실행하면 시간초과 + 메모리초과가 1,000,000% 발생한다.
따라서, 거듭제곱 역시 분할 정복 방식으로 수행 해야 한다.
다만, 최대 범위가 1,000,000 인 만큼, 분할 정복으로 거듭 제곱을 수행한다고 하더라도 메모리 초과가 발생할 것이다.
따라서, 거듭제곱을 할 때 주어진 mod 값인 1234567891 을 mod 한 값을 거듭제곱으로 수행하자.

백준 난이도 골드 1 정도의 문제라고 한다.
어쩐지 어렵더라, 혼자서 절 대 못 풀 어.. 구글링 안 했으면 평생 못 풀었어