โปรแกรมหาผลรวมความกว้างของทุก subsequence ใน Python

คำอธิบายโจทย์

ให้รายการ nums width ของ sequence = max - min หาผลรวม width ของทุก subsequence mod 10^9+7

ตัวอย่าง

nums = [7, 4, 9] → 15 (subsequences: [7],[4],[9],[7,4],[7,9],[4,9],[7,4,9] widths: 0,0,0,3,2,5,5)

วิธีแก้ปัญหา

Mathematical Formula + Sorting:

1. เรียง nums จากน้อยไปมาก
2. nums[i] เป็น max ใน 2^i - 1 subsequences (เลือก subset จาก i ตัวแรก)
3. nums[i] เป็น min ใน 2^(n-i-1) - 1 subsequences (เลือก subset จาก n-i-1 ตัวหลัง)
4. Contribution = nums[i] × ((2^i - 1) - (2^(n-i-1) - 1))
5. Precompute powers of 2 mod M

โค้ด Python

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(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))

อินพุต

[7, 4, 9]

เอาต์พุต

15