BOJ 1265 순열

순열의 $N$개의 값 중에서 앞쪽의 $i$개의 값을 먼저 확정한 상태를 생각해 봅시다. 이 상태에서 다음에 할 일은 $i+1$번째의 값을 정하는 것이 됩니다. 이때 다음과 같은 관찰을 할 수 있습니다.

• $i+1$번째 값은 $i+1-K$ 이상입니다. 즉, $i-K$ 이하인 수는 이미 모두 사용되었어야 합니다.
• $i$번째까지의 값에서 나올 수 있는 수는 $i+K$ 이하입니다. 즉, $i+K+1$ 이상의 수는 아직 사용되지 않았습니다.

따라서, 현재의 상태를 $i-K+1$ 이상 $i+K$ 이하의 수 중에서 사용된 것의 집합으로 표현할 수 있으며, 이는 $2K$개의 비트를 사용한 비트마스크로 표현할 수 있습니다.

초기 상태는 앞의 $K$비트가 켜진 것의 경우의 수를 1, 그 외는 0으로 두는 것이고, 마지막 출력 상태 또한 같습니다. 상태 전이는 다음과 같이 할 수 있습니다.

• 현재 상태에 $i+1-K$ 이상 $i+1+K$ 이하인 수 하나를 추가합니다.
• 그 수가 이미 상태에 존재했거나, 추가한 결과 맨 앞 비트가 1이 아니라면 무시합니다. (이 비트는 이후에 추가할 기회가 없습니다.)
• 맨 앞 비트를 제거하고 이전 상태의 경우의 수를 다음 상태에 더해 줍니다.

추가적으로, 이 문제에서 가장 큰 출력은 $N = 100, K = 6$일 때 71자리 수이므로, 파이썬 등 큰 수 연산이 지원되는 언어를 사용하거나 적당한 큰 수 구현체를 사용하여야 합니다.