快速幂的核心是二进制拆分与迭代更新，仅需res和base两个变量，时间O(log n)、空间O(1)，全程取模防溢出；指数为数组时应逐位用快速幂嵌套计算。
快速幂不是靠数组实现的，它的核心是二进制拆分与迭代更新，数组在这里通常只作为输入（比如指数以数字列表形式给出），而非算法主体结构。真正提升大规模数值运算效率的关键，在于避免直接展开高次幂，转而用位运算+模乘压缩计算路径。
为什么不用数组存中间幂？
有人误以为要预先用数组存下 a¹, a², a⁴, a⁸, … 再按需相乘——这看似直观，实则低效且危险：
- 数组长度取决于指数的二进制位数，对 10¹⁸ 级别指数，最多也就 60 项，看似不多，但每项都是大数，极易溢出或占用冗余内存；
- 实际只需两个变量：当前结果 res 和 当前底数幂 base，边算边更新，空间复杂度 O(1)；
- 预存数组无法应对取模场景（如 LeetCode 372 题要求 mod 1337），因为 a⁸ mod p ≠ (a⁴ mod p)² mod p 的中间值若未及时取模，会迅速越界。
数组作为指数输入时的正确处理方式
当指数本身以数组形式给出（例如 b = [1,0,2] 表示 102），不能先转成整数——它可能超 long long 范围。应结合「十进制逐位展开 + 快速幂嵌套」：
- 把 a^102 拆成 ((a¹)¹⁰ × a⁰)¹⁰ × a²，即从高位到低位扫描数组；
- 维护当前结果 res，每读一位 y，执行：
res = (res10 × ay) % MOD； - 其中 res¹⁰ 和 ay 都用快速幂函数计算，y ∈ {0,1,…,9}，非常小，可直接算或查表；
- 关键点：每次乘法后立即取模，不累积大数。
带模的快速幂标准模板（推荐迭代写法）
这是实战中最稳定、最易扩展的版本，适用于几乎所有大数幂场景（包括矩阵、多项式等满足结合律的运算）：
<font color="#888">def quick_pow(x: int, n: int, mod: int) -> int:
res = 1
base = x % mod
while n:
if n & 1:
res = (res * base) % mod
base = (base * base) % mod
n >>= 1
return res</font>- n & 1 判断二进制末位是否为 1，决定是否乘入当前 base；
- base = base * base % mod 实现底数平方并自动降维；
- 全程无递归、无数组、无大整数中间值，时间 O(log n)，空间 O(1)；
- mod 可替换为 1000000007、1337 或其他任意正整数。
典型实战场景举例
LeetCode 372. Super Pow：计算 a^[b₀,b₁,…,bₖ₋₁] mod 1337
- 输入 b 是数字列表，如 [2,1,3] → 指数为 213；
- 正确做法：从左到右遍历 b，初始 res = 1；
- 对每个数字 y：
res = quick_pow(res, 10, 1337)；
res = (res * quick_pow(a, y, 1337)) % 1337； - 这样避免构造 213，也规避了 10¹⁰⁰⁰⁰⁰ 级别整数，全程在 int 范围内完成。
