테페리넷

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

====== 영훈이의 색칠공부 ======

===== 풀이 =====
  * 먼저 빨간색만 색칠해보자. 색칠 방법은 N! 이다.
  * 이제 여기에 파란색을 색칠해보자. 각각의 열에 들어갈 행 번호가 모두 달라야 하고, 답이 될수 없는 번호가 하나씩 있다. n개의 원소가 모두 원래 위치에 있지 않게 배열하는 방법의 수와 같은 문제이므로 [[ps:tutorial:교란순열]]로 풀수 있다
    * 잘 안떠오르면 각 열들을 파란색이 색칠된 행의 번호순으로 정렬시켜놓고 생각하면 된다
  * 구해야 하는 답은 N!*D(N). 시간복잡도는 O(n)이다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 14578. 영훈이의 색칠공부".

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

Tags: [combinatoric]
"""

from teflib import combinatorics

MOD = 1_000_000_007


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


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency
    * [[:ps:teflib:combinatorics#factorial|teflib.combinatorics.factorial]]
    * [[:ps:teflib:combinatorics#derangement|teflib.combinatorics.derangement]]

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