LeetCode-2681 英雄的力量

Table of Contents

LeetCode-2681 英雄的力量 #

Solution 1 #

不要求序列连续, 所以可以先将数组排序, 以下讨论均基于排序后的 $nums$ . 考虑单个元素组成的序列, 这部分的值和为 $\sum_{0\leq i < n}nums^3[i]$ . 对于更多元素的序列, 假设最小值为 $nums[i]$ , 最大值为 $nums[j]$ , 那么一个序列的值为 $nums[i]\times nums^2[j]$ , 这样的序列有 $2^{j - i - 1}$ 个. 这部分的值和即为 $$ \sum_{0\leq i < j < n}nums[i]\times nums^2[j]\times 2^{j - i - 1} $$ 直接计算的话时间复杂度是 $O(n^2)$ , 考虑使用前缀和优化. 将上式改写为 $$ \sum_{0\leq i < n - 1}[\frac{nums[i]}{2^{i+1}}(\sum_{i < j < n}nums^2[j]\times 2^j)] \= \sum_{0\leq i < n - 1}[\frac{nums[i]}{2^{i+1}}(\sum_{0 < j \leq n - 1}nums^2[j]\times 2^j - \sum_{0 < j \leq i} nums^2[j]\times 2^j) ] $$ 可以使用 $O(n)$ 的时间预处理出 $\sum_{0\leq j \leq i}nums^2[j]\times 2^j$ , 从而可以在 $O(n)$ 的时间内计算出答案. 需要注意的是, 取模意义下的除法需要使用逆元进行处理.

using ll = long long;
const int MOD = 1e9 + 7;

class Solution {
public:
    // 快速幂
    ll power(ll x, ll n) {
        ll result = 1;
        while (n > 0) {
            if (n % 2 == 1) {
                result = (result * x) % MOD;
            }
            x = (x * x) % MOD;
            n /= 2;
        }
        return result;
    }

    // 逆元
    ll inverse(ll x) {
        return power(x, MOD - 2);
    }

    int sumOfPower(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<ll> sum(n, 0);
        for (int i = 0; i < n; i++) {
            sum[i] = ((nums[i] * 1LL) % MOD * nums[i] % MOD * power(2, i)) % MOD;
            if (i > 0) {
                sum[i] = (sum[i] + sum[i - 1]) % MOD;
            }
        }
        ll ans = 0;
        for (int i = 0; i < n - 1; i++) {
            ll coef = (nums[i] * 1LL * (sum[n - 1] - sum[i])) % MOD;
            coef = (coef * inverse(power(2, i + 1))) % MOD;
            ans = (ans + coef) % MOD;
        }
        for (int v : nums) {
            ans = (ans + ((v * 1LL * v) % MOD) * v) % MOD;
        }
        return ans >= 0? ans: ans + MOD;
    }
};

Solution 2 #

记 $dp[i]$ 为以 $nums[i]$ 为最大值 (也就是结尾) 的序列的最小值的和, 那么有 $$ dp[i] = nums[i] + \sum_{j = 0}^{i - 1}dp[j] $$ 目标即为 $$ \sum_{i = 0}^{n - 1}dp[i]\times nums^2[i] $$

using ll = long long;
const int MOD = 1e9 + 7;
class Solution {
public:
    int sumOfPower(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int dp = 0, preSum = 0; 
        int res = 0;
        for (int i = 0; i < n; i++) {
            dp = (nums[i] + preSum) % MOD;
            preSum = (preSum + dp) % MOD;
            res = (int) ((res + (ll) nums[i] * nums[i] % MOD * dp) % MOD);
            if (res < 0) {
                res += MOD;
            }
        }
        return res;
    }
};