배드민턴 대회

• 기본적인 교란순열 (Derangement) 문제. 참가자들이 4의 배수가 되도록 무작위로 3명 이하의 참가자를 제외하는 부분이 추가되었을 뿐이다
• 제외시킬 참가자는 N%4 명을 고르는 방법은 C(N, N%4) 이고, 4의 배수가 된 참가자 N-N%4 명이 모두 본인의 번호가 아닌 번호표를 뽑는 방법은 교란순열 D(4) 이다. 두 값을 곱해주면 된다
• 각각 O(n)에 구할수 있으므로 총 시간복잡도도 O(n)

"""Solution code for "BOJ 20443. 배드민턴 대회".

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

Tags: [combinatorics]
"""

from teflib import combinatorics

MOD = 1_000_000_007


def main():
    N = int(input())
    print(
        combinatorics.comb(N, N % 4, MOD)
        * combinatorics.derangement(N - N % 4, MOD)
        % MOD
    )


if __name__ == '__main__':
    main()

• Dependency
  • teflib.combinatorics.comb
  • teflib.combinatorics.derangement