本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
排序
题目
英雄的力量
给你一个下标从 0 开始的整数数组 nums ，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的 力量 定义为：
i0 ，i1 ，… ik 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i0],nums[i1] … nums[ik])2 * min(nums[i0],nums[i1] … nums[ik]) 。
请你返回所有可能的 非空 英雄组的 力量 之和。由于答案可能非常大，请你将结果对 109 + 7 取余。
示例 1：
输入：nums = [2,1,4]
输出：141
解释：
第 1 组：[2] 的力量为 22 * 2 = 8 。
第 2 组：[1] 的力量为 12 * 1 = 1 。
第 3 组：[4] 的力量为 42 * 4 = 64 。
第 4 组：[2,1] 的力量为 22 * 1 = 4 。
第 5 组：[2,4] 的力量为 42 * 2 = 32 。
第 6 组：[1,4] 的力量为 42 * 1 = 16 。
第? ???7 组：[2,1,4] 的力量为 42??? * 1 = 16 。
所有英雄组的力量之和为 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141 。
示例 2：
输入：nums = [1,1,1]
输出：7
解释：总共有 7 个英雄组，每一组的力量都是 1 。所以所有英雄组的力量之和为 7 。
参数范围：
1 <= nums.length <= 105
1 <= nums[i] <= 109
分析
时间复杂度
排序O(nlogn)，枚举结尾O(n)，故总复杂度O(nlogn+n)
原理
英雄的选择有三种方式：一，子数组，选择部分元素，选择的元素必须连续。二，子系列，选择部分元素，这些元素不需要连续，但必须保持原来的顺序。三，任意选择。第三种情况，排序不影响结果，可以大大简化问题。
排序后，枚举结尾。只选择一个英雄，比较简单，不赘述。下表以能力分别为1,2,3,4的4个英雄来说明，选择两个及更多英雄的情况。
| {1,2} | ||
| {1,3}{1,2,3} | {2,3} | |
| {1,4}{1,2,4},{1,3,4}{1,2,3,4} | {2,4},{2,3,4} | {3,4} |
观察上表。
| 最小值索引为0，最大致索引为i(i>0)的数量为 | 2 ^( i-1) (1,2,4) |
| 最小值索引为1，最大致索引为i(i>1)的数量为 | 2 ^( i-2) (1,2) |
| … | |
| 也就是i+1，biPrePre 乘以2。 | |
| 除最小、最大元素外，中间x个元素可以选择和不选择，故共有2 ^ x 种选择，x等于0也符合。 |
核心代码
template class C1097Int { public: C1097Int(long long llData = 0) :m_iData(llData% MOD) { } C1097Int operator+(const C1097Int& o)const { return C1097Int(((long long)m_iData + o.m_iData) % MOD); } C1097Int& operator+=(const C1097Int& o) { m_iData = ((long long)m_iData + o.m_iData) % MOD; return this; } C1097Int& operator-=(const C1097Int& o) { m_iData = (m_iData + MOD - o.m_iData) % MOD; return this; } C1097Int operator-(const C1097Int& o) { return C1097Int((m_iData + MOD - o.m_iData) % MOD); } C1097Int operator(const C1097Int& o)const { return((long long)m_iData * o.m_iData) % MOD; } C1097Int& operator=(const C1097Int& o) { m_iData = ((long long)m_iData * o.m_iData) % MOD; return *this; } bool operator<(const C1097Int& o)const { return m_iData < o.m_iData; } C1097Int pow(long long n)const { C1097Int iRet = 1, iCur = *this; while (n) { if (n & 1) { iRet *= iCur; } iCur *= iCur; n >>= 1; } return iRet; } C1097Int PowNegative1()const { return pow(MOD - 2); } int ToInt()const { return m_iData; } private: int m_iData = 0;; }; class Solution { public: int sumOfPower(vector& nums) { sort(nums.begin(), nums.end()); C1097Int<> biRet,biPrePre; for (int i = 0; i < nums.size(); i++) { C1097Int<> self((long long)nums[i] * nums[i]); biRet += self * nums[i];//长度为1的串 biRet += self * biPrePre; biPrePre *= 2; biPrePre += nums[i]; } return biRet.ToInt(); } };
测试用例
template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { Solution slu; vector nums ; int res; nums = { 2, 1, 4 }; res = slu.sumOfPower(nums); Assert(141, res); nums = { 1,1,1 }; res = slu.sumOfPower(nums); Assert(7, res); nums = { 1, 2, 3, 4, 6, 4, 3, 2 }; res = slu.sumOfPower(nums); Assert(10636, res); nums = { 1000000000,1000000000 }; res = slu.sumOfPower(nums); Assert(999998978, res);
//CConsole::Out(res);
}
5月旧代码
class Solution { public: int sumOfPower(vector& nums) { std::sort(nums.begin(), nums.end()); C1097Int<> iPrePre,iPre,iRet; for (const auto& n : nums) { iPrePre *= 2; iPrePre += iPre; iPre = n; C1097Int<> iAdd = iPrePre + iPre; iAdd *= n; iAdd *= n; iRet += iAdd; } return iRet.ToInt(); } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 充满正能量得对大家说 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 算法终将统治宇宙，而我们统治算法。《喜缺全书》 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
