문제 요약 및 풀이
문제를 딱 보자 마다, 어디선가 봤던 건데… 하고 망설였는데,
결론적으로는 교란순열이었다. (맨날 점화식 까먹는 것 같다.)
1
2
3
i) 교란순열의 i번째 항을 d[i]라 하자.
ii) 주어진 수가 4의 배수 인 경우, d[i]를 반환한다.
iii) 주어진 수가 4의 배수가 아닌 경우, combination(i, i % 4) * d[i - (i % 4)] 를 반환한다.
iii)에서는 4의 배수를 맞추기 위해 빠지는 인원을 정하는 경우의 수를 따로 곱한 것이다.
풀이 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)
끝