[TOC]
贡献法
leetcode 2681
由于元素的顺序不影响答案，先排序。 设有 $a, b, c, d, e$ 五个数，顺序从小到大。 如果把 $d$ 当成最大值:
- 如果只选 $d$ 单独一个数, 那么力量为 $d^3$ 。
- 选 $a$ 为最小值，由于中间的 $b$ 和 $c$ 可选可不选，一共有 $2^2$ 种方案， 所以力量总和为 $d^2 \cdot a \cdot 2^2$ 。
- 选 $b$ 为最小值，由于中间的 $c$ 可选可不选，一共有 $2^1$ 种方案，所以力 量总和为 $d^2 \cdot b \cdot 2^1$ 。
- 选 $c$ 为最小值，只有 $2^0=1$ 种方案，所以力量总和为 $d^2 \cdot c \cdot 2^0$ 。 因此，当 $d$ 为最大值时， $d$ 及其左侧元素对答案的贡献为 \(d^3+d^2 \cdot\left(a \cdot 2^2+b \cdot 2^1+c \cdot 2^0\right)\) 令 $s=a \cdot 2^2+b \cdot 2^1+c \cdot 2^0$ ，上式为 \(d^3+d^2 \cdot s=d^2 \cdot(d+s)\) 继续，把 $e$ 当成最大值，观察 $s$ 如何变化，也就是 $a, b, c, d$ 作为最小值的 贡献: \(\begin{aligned} & a \cdot 2^3+b \cdot 2^2+c \cdot 2^1+d \cdot 2^{01} \\ = & 2 \cdot\left(a \cdot 2^2+b \cdot 2^1+c \cdot 2^0\right)+d \cdot 2^0 \\ = & 2 \cdot s+d \end{aligned}\) 这意味着，我们不需要枚举最小值，只需要枚举最大值，就可以把 $s$ 递推计 算出来。
class Solution:
def sumOfPower(self, nums: List[int]) -> int:
MOD = 10 ** 9 + 7
nums.sort()
ans = s = 0
for x in nums: # x 作为最大值
ans = (ans + x * x * (x + s)) % MOD
s = (s * 2 + x) % MOD # 递推计算下一个 s
return ans
Leetcode 题单
补充：取模问题
有涉及取模，一定要写成全部运算取模，这样能大大加快速度
如果让你计算 $1234-6789$ 的个位数，你会如何计算? 由于只有个位数会影响到乘积的个位数，那么 $4 \cdot 9=36$ 的个位数 6 就是答 案。 对于 $1234+6789$ 的个位数，同理， $4+9=13$ 的个位数 3 就是答案。 你能把这个结论抽象成数学等式吗? 一般地，涉及到取模的题目，通常会用到如下等式（上面计算的是 $m=10$ ) : \(\begin{aligned} & (a+b) \bmod m=((a \bmod m)+(b \bmod m)) \bmod m \\ & (a \cdot b) \bmod m=((a \bmod m) \cdot(b \bmod m)) \bmod m \end{aligned}\) 证明: 根据带余除法，任意整数 $a$ 都可以表示为 $a=k m+r$ ，这里 $r$ 相当 于 $a \bmod m$ 。那么设 $a=k_1 m+r_1, b=k_2 m+r_2$ 。 第一个等式: \(\begin{aligned} & (a+b) \bmod m \\ = & \left(\left(k_1+k_2\right) m+r_1+r_2\right) \bmod m \\ = & \left(r_1+r_2\right) \bmod m \\ = & ((a \bmod m)+(b \bmod m)) \bmod m \end{aligned}\) 第二个等式: \(\begin{aligned} & (a \cdot b) \bmod m \\ = & \left(k_1 k_2 m^2+\left(k_1 r_2+k_2 r_1\right) m+r_1 r_2\right) \bmod m \\ = & \left(r_1 r_2\right) \bmod m \\ = & ((a \bmod m) \cdot(b \bmod m)) \bmod m \end{aligned}\) 根据这两个恒等式，可以随意地对代码中的加法和乘法的结果取模。
