Alleys Construction

• 문제 자체는 1670과 동일하다. n/2번째 카탈랑 수 (Catalan Number)를 구하면 된다.
• 난이도를 올리는 것은, 이 카탈랑 수를 313109 로 나눈 나머지를 구하는 것. 313109는 소수이기는 하지만, n보다 작을 수 있기 때문에, 일반적인 방법으로는 안되고, N보다 작은 소수로 나눈 나머지 를 구하는 방법을 써야 한다
• 뤼카의 정리를 이용해서 처리하면, 시간복잡도는 O(P)의 전처리 이후, 각 쿼리를 O(logn/logP)에 계산할 수 있다 (P=303109)

"""Solution code for "BOJ 33229. Alleys Construction".

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

Tags: [catalan]
"""

import sys
from teflib import combinatorics


MOD = 313109


def main():
    cc = combinatorics.CombCalculatorForSmallMod(MOD)

    q = int(sys.stdin.readline())
    for _ in range(q):
        n = int(sys.stdin.readline())
        print(cc.comb(n, n // 2) * pow(n // 2 + 1, -1, MOD) % MOD)


if __name__ == '__main__':
    main()

• Dependency: teflib.combinatorics.CombCalculatorForSmallMod