ผลรวมความกว้างของซับซีเควลน์ใน C++

คำอธิบายปัญหา

ให้อาร์เรย์ A พิจารณา subsequence ทุกตัว (ไม่ว่าง) ความกว้าง = max - min หาผลรวมความกว้างของทุก subsequence modulo 10⁹+7

ตัวอย่าง

A = [3,1,2] → Output: 6
Subsequences: [1],[2],[3],[2,1],[2,3],[1,3],[2,1,3]
Widths: 0,0,0,1,1,2,2 → Sum = 6

แนวทางแก้ปัญหา: คณิตศาสตร์ + Sorting

เรียง A เรียงน้อยไปมาก สำหรับ A[i] (0-indexed):

• เป็น max ใน 2ⁱ subsequence (เลือก subset ใดก็ได้จาก i ตัวแรก)
• เป็น min ใน 2ⁿ⁻¹⁻ⁱ subsequence (เลือก subset ใดก็ได้จาก n-1-i ตัวหลัง)
• ส่วนร่วมต่อผลรวม = A[i] × (2ⁱ - 2ⁿ⁻¹⁻ⁱ)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
const lli MOD = 1e9+7;

class Solution {
    lli add(lli a, lli b) { return (a%MOD + b%MOD)%MOD; }
    lli sub(lli a, lli b) { return ((a%MOD - b%MOD) + MOD)%MOD; }
    lli mul(lli a, lli b) { return (a%MOD * b%MOD)%MOD; }
    
public:
    int sumSubseqWidths(vector<int>& a) {
        sort(a.begin(), a.end());
        int n = a.size();
        lli ans = 0, rcnt = 1; // rcnt = 2^i
        
        for(int i=0; i