C++排序、前缀和算法的应用：英雄的力量

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);

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();
}
};