알고리즘 기말고사

• 전체 경우의 수에서, k문제 중에 1문제 이상이 맞는 경우의 수를 빼주는 방식으로 구할수 있다.
• k문제 중에 1문제 이상이 맞는 경우의 수는 포함 배제의 원리 (PIE; Principle of Inclusion-Exclusion) 를 이용해서 구하면 된다. 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개가 틀리는 경우의 수는, 교란순열 (Derangement)을 이용해서 C(n-k,i)*D(k+i) 로 쓸 수 있다. 이 방법으로 풀어도 팩토리얼 값과 D값을 O(n)에 전처리해두는 방식으로 총 O(n)에 풀 수 있다.
• 실제로는 n이 워낙 작아서, 전처리 없이 매번 조합과 팩토리얼을 계산해도 충분히 빠르다.

"""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()

"""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()

• Dependency: teflib.combinatorics.derangement