돌아온 떡파이어

• 문제에서 요구하는 것을 식으로 정리하는 것은 간단하다. N개의 떡을 M-1 일 동안 기본 한개씩 먹는 것은 고정이고, 나머지 N-(M-1)개의 떡을 M-1 일로 나누는 방법의 가짓수를 구하면 되니까, C(N-(M-1)+(M-1)-1, M-1) = C(N-1, M-1)이다.
• 어려운 것은, 이것을 100007로 나눈 나머지를 구하는 것. 100007은 97*1031로 소인수분해되는 합성수이므로, 계산하기가 까다롭다. 이항 계수 (Binomial Coefficient)에서 설명한 방법을 사용해야 한다. C(N-1, M-1) % 97 과 C(N-1, M-1) % 1031을 각각 뤼카의 정리를 이용해서 계산한 뒤에, 그렇게 얻은 나머지들을 갖고서 연립 선형 합동식을 사용하여 최종 답을 구한다.
• 시간 복잡도는. C(N-1, M-1)을 P로 나눈 나머지를 구하는 데에, O(P)의 전처리와 O(logN/logP)의 계산이 필요하다. P=97,1031을 상수로 보면 q개의 쿼리를 처리하는 데에 O(qlogN). 연립 합동식을 푸는 시간은 N의 영향을 받지 않으므로 상수라고 생각할 수 있다. 결국 총 시간복잡도는 O(qlogN)

"""Solution code for "BOJ 15718. 돌아온 떡파이어".

- Problem link: https://www.acmicpc.net/problem/15718
- Solution link: http://www.teferi.net/ps/problems/boj/15718
"""

from teflib import combinatorics
from teflib import numtheory

MOD_FACTORS = (97, 1031)  # 100007 = 97 * 1031


def main():
    comb_tables = {p: combinatorics.CombTable(p - 1, p) for p in MOD_FACTORS}

    T = int(input())
    for _ in range(T):
        N, M = [int(x) for x in input().split()]
        if M == 1:
            print(1 if N == 0 else 0)
            continue
        elif M > N + 1:
            print(0)
            continue

        rems = []
        for p in MOD_FACTORS:
            comb_table = comb_tables[p]
            n, k = N - 1, min(M - 2, (N - 1) - (M - 2))
            rem = 1
            while n > 0:
                n, n_mod = divmod(n, p)
                k, k_mod = divmod(k, p)
                rem *= comb_table.get(n_mod, k_mod)
            rems.append(rem % p)
        print(
            numtheory.linear_congruences(rems, MOD_FACTORS,
                                         coprime_moduli=True)[0])


if __name__ == '__main__':
    main()

• Dependency: teflib.combinatorics.CombTable, teflib.numtheory.linear_congruences