Luobuyu's Blog

0%

2681. 英雄的力量

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.4k 阅读时长 ≈ 1 分钟
推递推公式，和子数组还不一样。

2681.英雄的力量

题目描述：

给你一个下标从 0 开始的整数数组 nums ，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的 力量 定义为：

  • i0 ，i1 ，… ik 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i0],nums[i1] ... nums[ik])2 * min(nums[i0],nums[i1] ... nums[ik]) 。

请你返回所有可能的 非空 英雄组的 力量 之和。由于答案可能非常大，请你将结果对 109 + 7 取余。

数据范围：

$1\le nums.len \le 10^5,1\le nums[i] \le 10^9$

题解：

这个题目和子数组还不太一样，子数组的话就不能排序了。

这个题可以直接排序。如果是排序之后求子数组的，那就非常简单，直接前缀和就能得到。

但是这个是组合，组合与次序无关，可以排序，排序之后考虑针对某一个起点的贡献。

假如考虑 $a_i$ ，那么 $a_i$ 作为最小值，贡献为 $a_i \times (a_i^2 + a_{i + 1} ^ 2 + 2^1 \times a_{i + 2}^2 + 2^2 \times a_{i + 3}^2 + \cdots + 2^{j - i} \times a_{j}^2)$

为什么与 $2^i$ 有关呢，因为如果确定了起点 $a_i$ ，终点 $a_j$ ，那么中间的元素取与不取都是可以的，所以是中间元素的所有的子集。

观察该式子，发现后面一段可以递推得到，也就是 $a_{i + 1} ^ 2 + 2^1 \times a_{i + 2}^2 + 2^2 \times a_{i + 3}^2 + \cdots + 2^{j - i} \times a_{j}^2)$ 。前面的 $a_i^2$ 可以每次处理到的时候再加。因此可以使用一个 $sum$ 维护后面一段的和，然后从后往前，每次 $sum \times 2 + a_{i + 1}^2$ ，最后需要把 $a_i^2$ 加进去，然后乘以 $a_i$ 。

同样也可以枚举终点，然后求关于起点的递推式。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    const long long mod = 1e9 + 7;
    int sumOfPower(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        long long sum = 0;
        long long ans = 0;
        for (int i = n - 1; i >= 0; --i)
        {
            if (i + 1 == n)
                sum = 0;
            else
                sum = (sum * 2 + 1ll * nums[i + 1] * nums[i + 1] % mod) % mod;

            ans = (ans + nums[i] * (sum + 1ll * nums[i] * nums[i] % mod)) % mod;
        }
        return ans;
    }
};