우리에게 숫자 n이 주어지고 n까지의 양의 정수로 가능한 모든 순열을 작성하라는 요청을 받았다고 가정합니다. 순열은 사전순으로 정렬되고 1에서 n까지 번호가 매겨집니다. 모든 순열 중 하나의 순열을 취하여 특수 순열이라고 합니다. 이제 특수 순열 중에서; 가치를 잊을 수 있습니다. 잊은 값은 0으로 대체됩니다. 원래 순열과 같을 수 있는 순열을 찾은 다음 원근 번호를 추가하여 합계를 구해야 합니다. 합계 값은 프로그램의 출력으로 반환됩니다.
따라서 입력이 특수 순열(input_arr) =[0, 2, 0], n =3과 같으면 출력은 7이 됩니다. 두 가지 가능한 순열이 있을 수 있습니다. 하나는 [1, 2, 3]이고 다른 하나는 [3, 2, 1]입니다. 이러한 순열의 수는 각각 2와 5입니다. 따라서 결과는 5 + 2 =7이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 모드 :=10^9 + 7
- i2 :=2 ^ (모듈로 - 2) 모듈로
- fact :=값 1을 포함하는 새 목록
- 1 ~ n+1 범위의 x에 대해
- 팩트의 끝에 모듈로 모듈로(팩트의 마지막 항목 * x) 삽입
- cnt :=input_arr에서 0이 발생한 횟수
- cnt가 0과 같으면
- res :=0
- seen_list :=새 목록
- 1부터 시작하는 각 인덱스 i와 input_arr의 항목 x에 대해 다음을 수행합니다.
- tmp_val :=x가 정렬된 순서를 유지하면서 seeList에 삽입될 수 있는 인덱스
- res :=res + 사실[n-i] *(x - 1 - tmp_val)
- res :=res 모듈로
- tmp_val 위치의 seen_list에 x 삽입
- return + 1
- 그렇지 않으면
- ik :=(cnt ^ (modulo-2)) 모듈로
- miss :=True 값으로 초기화된 크기 n의 새 목록
- input_arr의 각 x에 대해 다음을 수행합니다.
- x가 0과 같지 않으면
- 미스[x - 1] :=거짓
- x가 0과 같지 않으면
- miss_srtd :=새 목록
- tmp :=0
- 1부터 시작하는 각 인덱스 i와 미스의 항목 x에 대해 다음을 수행합니다.
- x가 0이 아니면
- miss_srtd 끝에 i 삽입
- tmp :=tmp + i
- x가 0이 아니면
- pre :=0으로 초기화된 새 목록
- 미스에 있는 각 x에 대해 다음을 수행합니다.
- pre[-1] + x를 pre의 끝에 삽입
- cnt_cu :=0
- s :=tmp 모드 모듈로 * ik 모드 모듈로
- srtdw :=새 목록
- res :=0
- z :=0
- 1부터 시작하는 각 인덱스 i와 input_arr의 항목 x에 대해 다음을 수행합니다.
- x가 0이 아니면
- l :=정렬된 순서를 유지하면서 x가 srtdw에 삽입될 수 있는 위치
- tmp_val :=정렬된 순서를 유지하면서 x가 srtdw에 삽입될 수 있는 위치
- l :=l + z * (정렬된 순서를 유지하면서 x가 miss_srtd에 삽입될 수 있는 위치) modulo * ik modulo
- p :=x - 1 - l
- p :=p * 사실[cnt]
- p :=p 모듈로
- tmp_val 위치의 srtdw에 x 삽입
- cnt_cu :=cnt_cu + cnt - pre[x]
- 그렇지 않으면
- l :=cnt_cu
- l :=l * ik
- l :=l + z * i2 모듈로
- p :=s - 1 - l
- p :=p * 사실[cnt]
- p :=p 모듈로
- z :=z + 1
- res :=res + p * 사실[n-i] 모듈로
- res :=res 모듈로
- x가 0이 아니면
- return(res + fact[cnt]) 모듈로
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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