테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 배드민턴 대회 ======

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

===== 코드 =====
<dkpr py>
"""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()

</dkpr>
  * Dependency
    * [[:ps:teflib:combinatorics#comb|teflib.combinatorics.comb]]
    * [[:ps:teflib:combinatorics#derangement|teflib.combinatorics.derangement]]

{{tag>BOJ ps:problems:boj:골드_3}}