[BOJ 25964] 헨젤과 그레텔

문제: https://www.acmicpc.net/problem/25964

 

힌트:

이 문제에서 $N=K$인 경우, 구하는 수는 교란수 (https://en.wikipedia.org/wiki/Derangement)와 직접적인 관련이 있습니다.

풀이:

헨젤이 떨어뜨린 돌로 가능한 경우의 수는 $\frac{N!}{(N-K)!}$ 입니다.

이제 그레텔이 떨어뜨린 돌로 가능한 경우의 수를 구하기 위한 포함 배제 원리를 사용합시다.

 

헨젤과 그레텔의 돌 중 정해진 $i$개가 겹치는 경우의 수를 생각하면, 정해진 $i$개를 제외하고 나머지는 $N-i$개 중 $K-i$개를 고르는 경우의 수이기 때문에 $\frac{(N-i)!}{(N-K)!}$입니다. 정해진 $i$개를 고르는 방법은 $\binom{K}{i} = \frac{K!}{(K-i)! i!}$ 입니다. 이를 포함배제 식에 그대로 사용하면, 총 경우의 수는 $\frac{N!}{(N-K)!} \sum_{i=0}^K (-1)^i \frac{(N-i)! K!} {(N-K)! (K-i)! i!}$ 입니다.

 

저는 조금 더 정리된 식인, $\frac{N!K!}{\left((N-K)!\right)^2} \sum_{i=0}^K (-1)^i \frac{(N-i)!} { (K-i)! i!}$을 사용했습니다. 유도가 잘 이해되지 않으면, 교란수의 유도를 따라가 보는 것이 좋을 것 같습니다. (Derivation by inclusion–exclusion principle 문단)

 

코드: https://www.acmicpc.net/source/share/069a4fb8582d470f8dce36169b9a4d15 (Atcoder Library)