선물 전달

• 기본적인 교란순열 (Derangement) 문제.
• 모듈러가 소수가 아니기 때문에, 팩토리얼의 역수를 곱하는 일반식으로는 계산이 좀 어렵다. 덧셈과 곱셈으로만 이루어진 점화식을 사용하자.
• 시간복잡도는 O(n)

"""Solution code for "BOJ 1947. 선물 전달".

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

Tags: [derangement]

(This code was generated by Import Inliner v1.2)
"""

MOD = 1_000_000_000


# >>> Lines added by Import Inliner <<<
# - teflib.combinatorics.derangement [v0.1] (copied from teflib/combinatorics.py)
def derangement(n, mod=0):
    """Compute derangement D(n) % mod, in O(n). (D(1)=0, D(2)=1, D(3)=2, ...)"""
    if n == 1:
        return 0
    cur, prev = 1, 0
    for i in range(3, n + 1):
        cur, prev = (i - 1) * (cur + prev), cur
        if mod:
            cur %= mod
    return cur


# >>> Lines from original source code <<<
def main():
    N = int(input())
    print(derangement(N, MOD))


if __name__ == '__main__':
    main()

• Dependency: teflib.combinatorics.derangement