테페리넷

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

===== 풀이 =====
  * 전체 경우의 수에서, k문제 중에 1문제 이상이 맞는 경우의 수를 빼주는 방식으로 구할수 있다.
  * k문제 중에 1문제 이상이 맞는 경우의 수는 [[ps:tutorial:PIE]] 를 이용해서 구하면 된다. k개중에서 i개가 확실히 맞는 경우의 수를 f(i) 라고 하면 f(i) = C(k,i)*(n-i)! 로 쓸수 있다. 그리고 k문제 중에 1문제 이상이 맞는 경우의 수는 f(1)-f(2)+f(3)... -(-1)^k*f(k) 가 된다.
  * O(n) 에 팩토리얼 값을 전처리 해두면, 조합과 팩토리얼을 모두 O(1)에 구할수 있으므로 총 시간복잡도는 O(n)이 된다.
  * 여집합을 구하지 않고 바로 첫 k개가 모두 틀리는 경우의 수를 구하려면, 첫 k개만 틀리는 경우, 첫 k개와 추가로 1개가 틀리는 경우, 첫 k개와 추가로 2개가 틀리는 경우,.. 로 나누어서 합을 구하는 방법도 있다.
  * 첫 k개와 i개가 틀리는 경우의 수는, [[ps:tutorial:교란순열]]을 이용해서 C(n-k,i)*D(k+i) 로 쓸 수 있다. 이 방법으로 풀어도 팩토리얼 값과 D값을 O(n)에 전처리해두는 방식으로 총 O(n)에 풀 수 있다.
  * 실제로는 n이 워낙 작아서, 전처리 없이 매번 조합과 팩토리얼을 계산해도 충분히 빠르다.

===== 코드 =====

==== 코드 1 - 포함배제 ====
<dkpr py>
"""Solution code for "BOJ 9472. 알고리즘 기말고사".

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

Tags: [inclusion-exclusion]
"""

import math
import sys


def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        case_no, N, k = [int(x) for x in sys.stdin.readline().split()]

        answer = 0
        for i in range(k + 1):
            sign = 1 if i % 2 == 0 else -1
            answer += sign * math.comb(k, i) * math.factorial(N - i)

        print(case_no, answer)


if __name__ == '__main__':
    main()
</dkpr>

==== 코드 2 - 교란수열 ====
<dkpr py>
"""Solution code for "BOJ 9472. 알고리즘 기말고사".

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

Tags: [combinatorics]
"""

from teflib import combinatorics
import math
import sys


def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        case_no, N, k = [int(x) for x in sys.stdin.readline().split()]

        answer = sum(
            math.comb(N - k, i) * combinatorics.derangement(k + i)
            for i in range(N - k + 1)
        )
        print(case_no, answer)


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

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