Chương trình tính tổng các tổng chuỗi con liên tiếp đã sắp xếp trong khoảng cho trước bằng Python

Cho mảng nums gồm n số nguyên dương. Tính tổng của tất cả các chuỗi con liên tiếp không rỗng, sắp xếp chúng theo thứ tự không giảm để tạo mảng mới có n(n+1)/2 phần tử. Tìm tổng các phần tử từ chỉ số left đến right (đánh chỉ số từ 1) trong mảng mới. Kết quả modulo 10^9 + 7.

Ví dụ: nums = [1,5,2,6], left = 1, right = 5. Các tổng chuỗi con: 1, 5, 2, 6, 6, 7, 8, 8, 13, 14. Sau sắp xếp: [1,2,5,6,6,7,8,8,13,14]. Tổng từ chỉ số 1 đến 5: 1+2+5+6+6 = 20.

Thuật toán giải quyết

• m := 10^9 + 7
• n := độ dài nums
• Tạo danh sách a rỗng.
• Với i từ 0 đến n-1:
  • Với j từ i đến n-1:
    • Nếu i == j: thêm nums[j] vào a.
    • Ngược lại: thêm (nums[j] + a[-1]) % m vào a (tận dụng tổng tiền tố).

Ví dụ triển khai

def solve(nums, left, right):
    m = 10**9 + 7
    n = len(nums)
    a = []
    for i in range(n):
        for j in range(i, n):
            if i == j:
                a.append(nums[j])
            else:
                a.append((nums[j] + a[-1]) % m)
    a.sort()
    sm = sum(a[left-1:right])
    return sm % m

nums = [1,5,2,6]
left = 1
right = 5
print(solve(nums, left, right))

Đầu vào

[1,5,2,6], 1, 5

Đầu ra

20