Tổng độ rộng dãy con trong C++

Cho mảng A, xét tất cả dãy con không rỗng. Độ rộng của dãy con = max - min. Tính tổng độ rộng của tất cả dãy con modulo 10^9+7.

Ví dụ: [3,1,2] → 6.

Giải thuật

1. Sắp xếp mảng A.
2. Với mỗi phần tử A[i], nó đóng vai trò là max trong 2^i dãy con (chọn từ i phần tử trước), và là min trong 2^(n-1-i) dãy con (chọn từ n-1-i phần tử sau).
3. Đóng góp của A[i] vào tổng: A[i] * (2^i - 2^(n-1-i)).
4. Duyệt i từ 0 đến n-1, tính tổng modulo.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
    lli add(lli a, lli b){ return ( (a % m) + (b % m) ) % m; }
    lli sub(lli a, lli b){ return ( ( (a % m) - (b % m) ) + m ) % m; }
    lli mul(lli a, lli b){ return ( (a % m) * (b % m) ) % m; }
    int sumSubseqWidths(vector<int>& a) {
        sort(a.begin(), a.end());
        int ans = 0;
        int n = a.size();
        lli rcnt = 1;
        for(int i = 0; i < n; i++){
            ans = add(ans, sub(mul(a[i], sub(rcnt, 1)), mul(a[n-1-i], sub(rcnt, 1))));
            rcnt <<= 1;
            rcnt %= m;
        }
        return ans;
    }
};
int main(){
    Solution ob;
    vector<int> v = {3,1,2};
    cout << (ob.sumSubseqWidths(v));
}

Đầu vào

{3,1,2}

Đầu ra

6