Giả sử chúng ta có một chuỗi s. Chúng ta phải thực hiện thao tác sau trên s cho đến khi chúng ta nhận được một chuỗi được sắp xếp -
-
Chọn chỉ số i lớn nhất sao cho 1 <=i <độ dài của s và s [i]
-
Chọn chỉ số j lớn nhất sao cho i <=j <độ dài của s và s [k]
-
Trao đổi hai ký tự ở chỉ số i - 1 và j.
-
Đảo ngược hậu tố khỏi chỉ mục i.
Chúng ta phải tìm số lượng các hoạt động cần thiết để làm cho chuỗi được sắp xếp. Câu trả lời có thể rất lớn nên kết quả trả về modulo 10 ^ 9 + 7.
Vì vậy, nếu đầu vào là s ="ppqpp", thì đầu ra sẽ là 2 vì
-
Trong hoạt động đầu tiên, i =3, j =4. trao đổi s [2] và s [4] để lấy s ="ppppq", sau đó đảo ngược chuỗi con từ chỉ mục 3. Bây giờ, s ="pppqp".
-
Trong phép toán thứ hai, i =4, j =4. trao đổi s [3] và s [4] để lấy s ="ppppq", sau đó đảo ngược chuỗi con từ chỉ mục 4, Bây giờ, s ="ppppq".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
d:=Một mảng có kích thước 26 và điền bằng 0
-
a:=0, t:=1
-
m:=10 ^ 9 + 7
-
n:=ASCII của 'a'
-
đối với mỗi chỉ mục i và ký tự c của s theo thứ tự ngược lại, bắt đầu chỉ mục từ 1, làm
-
j:=ASCII của c - n
-
d [j]:=d [j] + 1
-
a:=(a + tổng tất cả các phần tử của d [từ chỉ số 0 đến j-1]) * thương số của t / d [j]) mod m
-
t:=t * thương số của i / d [j]
-
-
trả lại một
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn
def solve(s):
d = [0]*26
a = 0
t = 1
m = 10**9 + 7
n = ord('a')
for i,c in enumerate(s[::-1],1):
j = ord(c) - n
d[j] += 1
a = (a+sum(d[:j])*t//d[j]) % m
t = t*i//d[j]
return a
s = "ppqpp"
print(solve(s)) Đầu vào
"ppqpp"
Đầu ra
2