양의 정수 1부터 n까지를 한 번씩 사용해 만들 수 있는 모든 순열을 생각해 봅시다. 이 순열들을 사전순(lexicographic order)으로 정렬한 뒤 1번부터 차례대로 번호를 매깁니다. 그중 하나의 순열을 '특별한 순열'이라고 하는데, 이 순열의 일부 값이 지워져서 0으로 대체되었다고 가정합니다. 우리가 해야 할 일은 0으로 가려진 자리를 채워 원래 순열이 될 수 있는 모든 후보 순열을 찾고, 각 후보의 번호를 모두 더한 합을 구하는 것입니다.
예를 들어 특별한 순열이 [0, 2, 0]이고 n = 3이라면 결과는 7이 됩니다. 0인 자리를 채워 만들 수 있는 순열은 [1, 2, 3]과 [3, 2, 1] 두 가지뿐입니다. 사전순으로 번호를 매기면 [1, 2, 3]은 1번, [3, 2, 1]은 6번이므로 1 + 6 = 7이 정답입니다.
핵심 아이디어
사전식 순위(lexicographic rank)의 기본 원리는 다음과 같습니다. 각 위치에서 '현재 값보다 작으면서 아직 사용되지 않은 값'의 개수만큼 그 앞에 올 수 있는 순열이 존재하며, 남은 자리의 수를 k라고 할 때 그 기여도는 (작은 값의 개수) × k! 입니다. 값이 지워진 경우에는 빠진 값들의 평균 순위를 모듈러 곱셈 역원을 이용해 계산해 같은 방식으로 기여도를 더하고, 마지막에 지워진 자리의 경우의 수(cnt!)를 보정해 줍니다. 모든 연산은 10^9 + 7로 나눈 나머지로 처리해 값이 지나치게 커지는 것을 방지합니다.
단계별 알고리즘
문제를 해결하기 위해 다음 단계를 따릅니다.
- mod := 10^9 + 7 로 설정합니다.
- i2 := 2^(mod − 2) mod mod (2의 모듈러 역원)를 계산합니다.
- fact := 1을 초기값으로 하는 팩토리얼 리스트를 만들고, x를 1부터 n까지 순회하며 fact의 마지막 값에 x를 곱한 뒤 mod로 나눈 나머지를 추가합니다.
- cnt := input_arr에서 0의 개수
- cnt가 0인 경우(모든 값이 확정된 경우):
- res := 0, seen_list := 빈 리스트
- i를 1부터 매기며 input_arr의 각 요소 x에 대해:
- tmp_val := x가 seen_list에 정렬 순서를 유지한 채 삽입될 위치
- res := res + fact[n−i] × (x − 1 − tmp_val), res := res mod mod
- seen_list의 tmp_val 위치에 x를 삽입
- res + 1을 반환합니다.
- 그 외의 경우(0이 하나 이상 존재하는 경우):
- ik := cnt^(mod − 2) mod mod (cnt의 모듈러 역원)
- miss := 길이 n의 리스트를 True로 초기화하고, input_arr의 0이 아닌 값 x에 대해 miss[x−1] := False로 설정
- miss_srtd := 빠진 값들의 오름차순 리스트, tmp := 빠진 값들의 합
- pre := miss의 누적합 리스트(첫 값은 0)
- cnt_cu := 0, s := tmp mod mod × ik mod mod, srtdw := 빈 리스트, res := z := 0
- i를 1부터 매기며 input_arr의 각 요소 x에 대해:
- x가 0이 아니면:
- l := tmp_val := x가 srtdw에 삽입될 위치
- l := l + z × (x가 miss_srtd에 삽입될 위치) mod mod × ik mod mod
- p := (x − 1 − l) × fact[cnt] mod mod
- srtdw의 tmp_val 위치에 x를 삽입
- cnt_cu := cnt_cu + cnt − pre[x]
- x가 0이면:
- l := cnt_cu × ik + z × i2 mod mod
- p := (s − 1 − l) × fact[cnt] mod mod
- z := z + 1
- res := res + p × fact[n−i] mod mod, res := res mod mod
- x가 0이 아니면:
- (res + fact[cnt]) mod mod를 반환합니다.
예제 구현
아래 구현을 통해 더 잘 이해해 봅시다.
import bisect
def solve(input_arr, n):
modulo = 10 ** 9 + 7
i2 = pow(2, modulo-2, modulo)
fact = [1]
for x in range(1, n+1):
fact.append(fact[-1] * x % modulo)
cnt = input_arr.count(0)
if not cnt:
res = 0
seen_list = []
for i, x in enumerate(input_arr, 1):
tmp_val = bisect.bisect(seen_list, x)
res += fact[n-i] * (x - 1 - tmp_val)
res %= modulo
seen_list.insert(tmp_val, x)
return res + 1
else:
ik = pow(cnt, modulo-2, modulo)
miss = [True] * n
for x in input_arr:
if x != 0: miss[x-1] = False
miss_srtd = []
tmp = 0
for i, x in enumerate(miss, 1):
if x:
miss_srtd.append(i)
tmp += i
pre = [0]
for x in miss:
pre.append(pre[-1] + x)
cnt_cu = 0
s = tmp % modulo * ik % modulo
srtdw = []
res = z = 0
for i, x in enumerate(input_arr, 1):
if x:
l = tmp_val = bisect.bisect(srtdw, x)
l += z * bisect.bisect(miss_srtd, x) % modulo * ik % modulo
p = x - 1 - l
p *= fact[cnt]
p %= modulo
srtdw.insert(tmp_val, x)
cnt_cu += cnt - pre[x]
else:
l = cnt_cu
l *= ik
l += z * i2 % modulo
p = s - 1 - l
p *= fact[cnt]
p %= modulo
z += 1
res += p * fact[n-i] % modulo
res %= modulo
return (res + fact[cnt])%modulo
print(solve([0, 2, 0], 3))
입력
[0, 2, 0], 3
출력
7
bisect 모듈을 사용하면 삽입 위치 탐색은 O(log n)에 수행되지만, 리스트 삽입 자체는 선형 시간이 걸리므로 전체 시간 복잡도는 최악의 경우 O(n²)이며, 추가 공간 복잡도는 O(n)입니다. 이 방식은 값이 모두 주어진 일반 순열의 순위 계산 문제와, 값이 일부 지워진 경우의 확률적·평균적 기대 기여도 계산 문제를 하나의 틀로 통합해 처리한다는 점에서 유용합니다.