[BOJ] 20443 배드민턴 대회

문제 요약 및 풀이

20443번: 배드민턴 대회

문제를 딱 보자 마다, 어디선가 봤던 건데… 하고 망설였는데,

결론적으로는 교란순열이었다. (맨날 점화식 까먹는 것 같다.)

i) 교란순열의 i번째 항을 d[i]라 하자.
ii) 주어진 수가 4의 배수 인 경우, d[i]를 반환한다.
iii) 주어진 수가 4의 배수가 아닌 경우, combination(i, i % 4) * d[i - (i % 4)] 를 반환한다.

iii)에서는 4의 배수를 맞추기 위해 빠지는 인원을 정하는 경우의 수를 따로 곱한 것이다.

풀이 코드

MOD = 1_000_000_007
derangement = [1, 0, 1, 2, 9]

for i in range(5, 110):
  derangement.append(((i-1) * (derangement[-1] + derangement[-2])) % MOD)

def nCr(n, k):
  ret = 1
  for i in range(n, n-k, -1):
    ret *= i
  for i in range(1, k+1):
    ret //= i
  return ret

n = int(input())
k = n % 4
print((derangement[n - k] * nCr(n, k)) % MOD)

끝