Giả sử, chúng ta được cho một số n và được yêu cầu viết tất cả các hoán vị có thể có với các số nguyên dương lên đến n. Các hoán vị sau đó được sắp xếp theo từ điển và đánh số từ 1 đến n. Trong số tất cả các hoán vị, một hoán vị được thực hiện và được gọi là hoán vị đặc biệt. Bây giờ, trong số các hoán vị đặc biệt; các giá trị có thể bị lãng quên. Các giá trị bị quên sau đó được thay thế bằng các số 0. Chúng ta phải tìm các hoán vị có thể bằng với các hoán vị ban đầu và sau đó chúng ta cộng số phối cảnh của chúng để thu được một tổng. Giá trị tổng được trả về dưới dạng đầu ra của chương trình.
Vì vậy, nếu đầu vào giống như hoán vị đặc biệt (input_arr) =[0, 2, 0], n =3, thì đầu ra sẽ là 7. Có thể có hai hoán vị. Một là [1, 2, 3] và một là [3, 2, 1]. Số các hoán vị này lần lượt là 2 và 5. Vì vậy, kết quả sẽ là 5 + 2 =7.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- mod:=10 ^ 9 + 7
- i2:=2 ^ (modulo - 2) mod modulo
- fact:=một danh sách mới chứa giá trị 1
- đối với x trong phạm vi từ 1 đến n + 1, thực hiện
- insert (item cuối cùng của sự kiện * x) modulo vào cuối sự thật
- cnt:=số lần xuất hiện của 0 trong input_arr
- nếu cnt giống 0, thì
- res:=0
- saw_list:=một danh sách mới
- đối với mỗi chỉ mục tôi bắt đầu từ 1 và mục x trong input_arr, hãy thực hiện
- tmp_val:=chỉ số nơi x có thể được chèn vào sawList để duy trì thứ tự đã sắp xếp
- res:=res + fact [n-i] * (x - 1 - tmp_val)
- res:=res mod modulo
- chèn x vào saw_list ở vị trí tmp_val
- trả lại res + 1
- nếu không,
- ik:=(cnt ^ (modulo-2)) mod modulo
- miss:=một danh sách mới có kích thước n được khởi tạo với giá trị True
- đối với mỗi x trong input_arr, hãy thực hiện
- nếu x không giống 0, thì
- miss [x - 1]:=False
- nếu x không giống 0, thì
- miss_srtd:=một danh sách mới
- tmp:=0
- đối với mỗi chỉ mục tôi bắt đầu từ 1 và mục x thiếu, hãy thực hiện
- nếu x khác 0, thì
- chèn tôi vào cuối miss_srtd
- tmp:=tmp + i
- nếu x khác 0, thì
- pre:=một danh sách mới được khởi tạo bằng 0
- đối với mỗi x in miss, do
- chèn pre [-1] + x vào cuối pre
- cnt_cu:=0
- s:=tmp mod modulo * ik mod modulo
- srtdw:=một danh sách mới
- res:=0
- z:=0
- đối với mỗi chỉ mục tôi bắt đầu từ 1 và mục x trong input_arr, hãy thực hiện
- nếu x khác 0, thì
- l:=vị trí mà x có thể được chèn vào srtdw để duy trì thứ tự đã sắp xếp
- tmp_val:=vị trí có thể chèn x vào srtdw để duy trì thứ tự đã sắp xếp
- l:=l + z * (vị trí mà x có thể được chèn vào miss_srtd duy trì thứ tự đã sắp xếp) mod modulo * ik mod modulo
- p:=x - 1 - l
- p:=p * fact [cnt]
- p:=p mod modulo
- chèn x vào srtdw ở vị trí tmp_val
- cnt_cu:=cnt_cu + cnt - pre [x]
- nếu không,
- l:=cnt_cu
- l:=l * ik
- l:=l + z * i2 mod mô đun
- p:=s - 1 - l
- p:=p * fact [cnt]
- p:=p mod modulo
- z:=z + 1
- môđun res:=res + p * fact [n-i]
- res:=res mod modulo
- nếu x khác 0, thì
- mô-đun mô-đun return (res + fact [cnt])
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
[0, 2, 0], 3
Đầu ra
7