Chương trình tìm tổng độ rộng của tất cả dãy con của danh sách số trong Python

Cho danh sách nums. Độ rộng dãy = max - min. Tính tổng độ rộng của tất cả dãy con (subsequence). Kết quả modulo 10^9+7.

Ví dụ: nums = [7, 4, 9] → 15. Các dãy con: [7],[4],[9],[7,4],[7,9],[4,9],[7,4,9] độ rộng: 0,0,0,3,2,5,5.

Giải pháp

Sắp xếp nums. Mỗi phần tử nums[i] đóng góp:

• Là max trong 2^i - 1 dãy con (chọn subset từ i phần tử trước)
• Là min trong 2^(n-i-1) - 1 dãy con (chọn subset từ n-i-1 phần tử sau)
• Đóng góp = nums[i] * ((2^i - 1) - (2^(n-i-1) - 1))
• Tính trước powers of 2 modulo MOD

Ví dụ minh họa

class Solution:
    def solve(self, nums):
        m = 10**9 + 7
        nums.sort()
        ans = 0
        power = [1] * (len(nums) + 1)
        for i in range(1, len(nums) + 1):
            power[i] = power[i - 1] * 2 % m
        for i in range(0, len(nums)):
            positive = (power[i] - 1) * nums[i]
            negative = (power[len(nums) - i - 1] - 1) * nums[i]
            ans = (ans + positive - negative) % m
        return ans

ob = Solution()
nums = [7, 4, 9]
print(ob.solve(nums))

Đầu vào

[7, 4, 9]

Đầu ra

15