algo-aha

所有子序列的最大最小差值之和

• https://leetcode.com/problems/sum-of-subsequence-widths/

int sumSubseqWidths(vector<int>& A) {
    // 子序列的最大最小值，与顺序无关，排序数组
    // 比A[i]大的数有N-1-i个，A[i]作最小值的子序列有2^(N-1-i)个，A[i]对ans贡献2^(N-1-i)*(-A[i])
    // 比A[i]小的数有i个，A[i]作最大值的子序列有2^i个，对ans贡献2^i*A[i]
    // 所以，A[i]对ans贡献 A[i] * (2^i - 2^(N-1-i))
    sort(A.begin(), A.end());
    const int N = A.size(), MOD = 1e9 + 7;
    vector<int> pow2(N);
    pow2[0] = 1;
    for (int i = 1; i < N; i++) {
        pow2[i] = (pow2[i-1] << 1) % MOD;
    }
    
    int ans = 0;
    for (int i = 0; i < N; i++) {
        ans = (ans + (long)A[i] * (pow2[i] - pow2[N-1-i])) % MOD;
    }
    return ans;
}

所有满足 子序列最大最小之和<=target 的子序列个数

• https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/

int numSubseq(vector<int>& A, int target) {
    // 子序列的最大最小值与顺序无关，排序数组
    sort(A.begin(), A.end());
    // 预先计算pow2[]
    const int N = A.size(), MOD = 1e9 + 7;
    vector<int> pow2(N);
    pow2[0] = 1;
    for (int i = 1; i < N; i++) {
        pow2[i] = (pow2[i-1] << 1) % MOD;
    }
    // 对A[i]，找A[i]+A[j]<=target的最大j，两指针法
    int ans = 0;
    for (int i = 0, j = N - 1; i <= j; ) {
        if (A[i] + A[j] > target) {
            j--;
        } else {
            // 非空子序列，选了A[i]后，(i..j]间的数可选或不选，有2^(j-i)种可能
            ans = (ans + pow2[j-i]) % MOD;
            i++;
        }
    }
    return ans;
}

所有奇数长子段的总和

• https://leetcode.com/problems/sum-of-all-odd-length-subarrays/

int sumOddLengthSubarrays(vector<int>& A) {
    // 看A[i]对奇数长子段贡献了多少值
    // 左边包含A[i]的子段A[..i]有i+1个，右边包含A[i]的子段A[i..]有N-i个，包含A[i]的子段共(i+1)*(N-i)个。
    // 设包含A[i]的奇数子段有odd个，偶数子段有even个，由举例归纳的、应该没错的结论为 odd=even或even+1。
    // 注：比如举例统计[1 2 3 4 5]中包含2的长度1子段数、长度2子段数、长度3子段数...，
    // 所以奇数长子段有 odd = ((i+1)*(N-i)+1)/2个
    const int N = A.size();
    int ans = 0;
    for (int i = 0; i < N; i++) {
        ans += ((i+1)*(N-i)+1)/2 * A[i];
    }
    return ans;
}

联想：所有子段最小值的和