快速幂通过二进制拆分指数将时间复杂度从O(exp)降至O(log exp)，核心是每次底数平方、按位累乘，需用long long防溢出并每步取模；标准迭代模板简洁高效，适用于非负整数指数与整数底数。
快速幂的核心逻辑是二进制拆分指数
直接用 pow(base, exp) 算大指数（比如 exp > 1e9）会超时或溢出，因为它是 O(exp) 的线性乘法。快速幂把指数看作二进制位，每次将底数平方、根据当前位是否为 1 决定是否累乘，时间降到 O(log exp)。
关键点在于：每轮迭代中，base 实际代表的是 base^(2^i)，而 exp 的第 i 位为 1 时，就把这一项乘进结果。
- 必须用
long long存结果和中间乘积，避免 int 溢出 - 模运算（如取模
MOD）要每步都做，不能只在最后取 —— 否则乘法中间就溢出 - 指数为 0 时直接返回 1（注意：0^0 通常按题意定义，一般不在此模板处理）
带取模的递归写法容易栈溢出，推荐迭代实现
递归版虽然直观，但深度达 ~60 层（log₂(1e18) ≈ 60）虽不算深，但在嵌入式或栈受限环境可能出问题；更重要的是，迭代更易控制模运算时机、也方便扩展为矩阵快速幂。
标准迭代模板如下（以 MOD = 1e9+7 为例）：
立即学习“C++免费学习笔记（深入）”；
const int MOD = 1e9 + 7;
long long quick_pow(long long base, long long exp) {
long long res = 1;
base %= MOD; // 防止 base 本身超 MOD
while (exp > 0) {
if (exp & 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp >>= 1;
}
return res;
}-
exp & 1比exp % 2 == 1更快且无符号安全 -
exp >>= 1等价于exp /= 2，但位运算更稳定 - 如果题目不要求取模，去掉所有
% MOD，但仍需保留long long和base %= MOD的等效检查（如改为if (base >= MOD) base %= MOD;）
负指数、浮点底数、大数字符串指数都不适用此模板
这个模板只处理「非负整数指数 + 整数底数」场景。遇到以下情况需另作处理：
- 负指数：C++ 原生不支持整数类型的负幂，需转成浮点或配合逆元（仅当模数为质数且底数非倍数时可用费马小定理）
- 底数是
double：快速幂逻辑不变，但要注意精度丢失，尤其指数大时结果可能为 inf 或 nan - 指数以字符串给出（如长度 1e5 的数字）：不能转
long long，得用高精度取模预处理指数（即计算exp % phi(MOD)，再套快速幂），这属于数论进阶内容，和本模板无关
矩阵快速幂只需改乘法为矩阵乘
把标量乘法换成 vector<vector long>></vector> 的乘法，其余结构完全一致。例如求斐波那契第 n 项，转移矩阵是 {{1,1},{1,0}}，快速幂算它 n-1 次方后乘初始向量即可。
唯一额外注意点：矩阵乘法的维度和模运算位置。例如 2×2 矩阵相乘，每项都要 % MOD，且中间用 long long 防止三项乘积累加溢出：
vector<vector<long long>> mat_mult(const vector<vector<long long>>& A, const vector<vector<long long>>& B) {
int n = A.size(), m = B[0].size(), p = B.size();
vector<vector<long long>> C(n, vector<long long>(m, 0));
for (int i = 0; i < n; i++)
for (int k = 0; k < p; k++)
for (int j = 0; j < m; j++)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
return C;
}真正容易漏掉的是：矩阵快速幂的单位矩阵初始化必须对角为 1、其余为 0，且大小要和输入矩阵一致 —— 错一维或少一个 % MOD，结果就全错。
