企业官网建设流程全解析

十进制快速幂和十进制矩阵快速幂，这两个词放在一起，很多人第一反应是“不就是把二进制快速幂换个进制吗”。真动手写过的人就知道，坑远比想象的多。我最早接触这个技巧是在处理一类指数大到离谱的题目——指数不是普通的long long，而是以十进制字符串形式给出的，长度动辄上万位。这种场景下，传统的二进制快速幂连指数都存不下，更别提逐位乘了。十进制快速幂解决的正是“指数以十进制形式超长给出”时的幂运算问题，而十进制矩阵快速幂则是它在矩阵幂场景下的推广，常用于超大指数下的线性递推加速。这篇内容适合已经会写普通快速幂、想进一步处理超长指数场景的读者，也适合正在啃矩阵加速递推、被大指数卡住的同学。下面我把自己从踩坑到跑通的全过程拆开讲，包括原理推导、代码实现、参数细节和那些文档里不会写的经验。

1. 先搞清楚它到底解决什么问题

1.1 从二进制快速幂的局限说起

普通快速幂的核心思想是把指数做二进制拆分，比如算a^13，把 13 拆成1101，也就是a^8 * a^4 * a^1，通过不断平方底数、按位判断是否累乘，把复杂度从 O(n) 降到 O(log n)。这套东西大家都很熟，代码也就十来行。但它有一个隐含前提：指数必须能放进一个整数类型里，才能做位移和取位操作。

问题就出在这个前提上。有些场景下指数是以十进制字符串给出的，长度可能是一万位甚至十万位。这时候你连把它转成long long都做不到，二进制拆分无从谈起。有人会说那就用大整数库，但大整数库做幂运算本身也是按指数规模走的，指数是 10^10000 这个量级，任何逐次累乘的方案都会直接超时。十进制快速幂的思路是：既然指数是十进制给的，那我就按十进制位来处理，从高位到低位扫描，每读一位就把当前结果做十次方，再乘上这一位的幂。这样扫描的复杂度是 O(指数位数)，每一位内部做常数次乘法，整体可控。

1.2 十进制快速幂的核心恒等式

整个技巧建立在一个很朴素的恒等式上。假设指数n的十进制表示是d_k d_{k-1} ... d_1 d_0，那么：

a^n = a^(d_k * 10^k + ... + d_1 * 10 + d_0)

按 Horner 法则从高位往低位扫，可以写成递推形式。设当前已经处理完前缀，得到结果res，读入下一位数字d，则新的指数对应：

res_new = res^10 * a^d

这个式子就是全部的核心。为什么是十次方？因为每往右读一位，前面已经累积的指数整体要左移一个十进制位，也就是乘以 10，对应到幂上就是做十次方。而新读入的这一位d贡献的是a^d，d只有 0 到 9 十种可能，可以预处理或者直接小循环算出来。

我一开始觉得这个式子太简单了，简单到怀疑它是不是有什么隐藏问题。实测下来它确实成立，但有几个细节必须注意，后面会专门讲。

1.3 和二进制快速幂的复杂度对比

很多人关心十进制快速幂是不是比二进制慢。从乘法次数上看，二进制快速幂处理一个 L 位的指数大约需要 L 次平方加若干次乘法，十进制快速幂处理一个 L 位的十进制指数需要 L 次“十次方”加 L 次小幂乘法。一次十次方需要约 4 次乘法（平方再平方再乘），所以常数上确实大一些。但关键在于：当指数以十进制字符串给出时，二进制方案根本没法用，十进制方案是唯一可行的路线。所以这不是“哪个更快”的问题，而是“哪个能用”的问题。

这张表我建议记一下，选型的时候先看指数是怎么给的，再决定用哪套。

2. 十进制快速幂的实现细节与参数取舍

2.1 从高位扫描还是从低位扫描

实现上有两种扫描方向。从高位往低位扫，用的是上面那个 Horner 递推，逻辑直观，符合我们读数字的习惯。从低位往高位扫，则需要维护一个“当前位的权重幂”，也就是a^(10^i)，每处理一位就把权重做十次方。两种都能work，但高位扫描的代码更短，状态更少，我一般首选高位扫描。

高位扫描的伪代码大概是这样：

res = 1 for each digit d in n (from most significant to least): res = res^10 res = res * a^d return res

注意a^d里d可能是 0，此时a^0 = 1，乘上去不影响结果，所以可以直接统一处理，不用特判。这一点比二进制快速幂舒服，二进制里遇到 0 位虽然也是乘 1，但很多人会写条件判断，十进制这里直接乘反而更干净。

2.2 模运算下的十次方怎么写才不溢出

实际题目几乎都带模数，所以所有乘法都要取模。十次方不能直接写res * res * ...十次，那样既慢又容易在中间过程溢出（即使用了long long，连续乘也可能超）。正确做法是用平方倍增：

long long pow10(long long x, long long mod) { long long x2 = x * x % mod; long long x4 = x2 * x2 % mod; long long x8 = x4 * x4 % mod; return x8 * x2 % mod; }

这里x^10 = x^8 * x^2，只需要三次平方加一次乘法，共四次乘法。每一步都取模，long long下两个小于模数的数相乘，只要模数在 10^9 量级就不会溢出。如果模数接近long long上限，那就得用快速乘或者__int128，这是另一个话题，后面问题排查里会提。

我见过有人图省事写循环十次乘，代码是短了，但常数大了一倍多，指数位数上万的时候差距很明显。这种地方该抠还是要抠。

2.3 小幂 a^d 的预处理策略

a^d中d只有 0 到 9，最直接的做法是每次读位时写个小循环乘d次。但更稳的做法是预处理一张表pow_a[0..9]，其中pow_a[i] = a^i mod m。预处理只需要 9 次乘法，之后每位 O(1) 查表。

pow_a[0] = 1; for (int i = 1; i <= 9; i++) pow_a[i] = pow_a[i-1] * a % mod;

这张表在指数位数很大时收益明显，因为每位都省掉了最多 9 次乘法。而且它让主循环体变得极简，只有一次十次方和一次查表乘法，读起来清爽，出错概率也低。

注意：预处理表里的a是原始底数取模后的值，不是每次十次方之后的结果。这一点新手容易搞混，把res当成底数去建表，那就全错了。

2.4 指数前导零和空串的边界处理

指数以字符串给出时，可能出现前导零，比如"000123"。高位扫描时前导零会让res连续做十次方再乘 1，结果不变，所以逻辑上不影响正确性，但会白白多跑几轮。稳妥的做法是先跳过前导零，从第一个非零位开始扫。如果整个串全是零，那指数就是 0，直接返回 1（模运算下返回1 % mod）。

空串属于非法输入，正常题目不会给，但自己写工具函数时最好加个判断，避免越界。这种边界看着琐碎，真在比赛或者工程里崩一次就长记性了。

3. 十进制矩阵快速幂的推广与实现

3.1 矩阵场景下恒等式依然成立

矩阵幂和标量幂在代数结构上是相通的，只要矩阵乘法满足结合律，上面那个 Horner 递推就照样成立。也就是说：

M^n = M^(d_k * 10^k + ... + d_0)

按高位扫描，每读一位做res = res^10 * M^d。这里res是矩阵，res^10是矩阵的十次方，M^d是矩阵的小幂。矩阵乘法不满足交换律，所以顺序不能乱：必须是先算res^10，再右乘M^d。因为递推里res代表的是已经处理的前缀对应的幂，新位是在指数低位追加，数学上M^(prefix * 10 + d) = (M^prefix)^10 * M^d，右乘是对的。如果你写成左乘，结果就错了，这是矩阵版最容易翻车的地方。

3.2 矩阵十次方的计算与优化

矩阵的十次方同样用平方倍增：先算A2 = A*A，再算A4 = A2*A2，A8 = A4*A4，最后A10 = A8 * A2。一共四次矩阵乘法。矩阵乘法是 O(k^3)，k 是矩阵阶数，所以常数比标量版大得多。如果指数位数上万，矩阵阶数又到了几十，那总运算量是相当可观的，必须把矩阵乘法本身写紧凑。

我一般把矩阵乘法写成三重循环加取模，内层用long long累加，累加完再取模。如果模数较小、阶数不大，也可以在内层就取模，看具体情况。关键是避免在累加过程中溢出，long long下累加 k 次、每次两个小于模数的数相乘，k 在百以内、模数在 10^9 量级时是安全的。

3.3 单位矩阵的初始化与结果矩阵

矩阵版的res初始必须是单位矩阵，不能是全 1 或者全 0。单位矩阵在矩阵乘法里扮演标量 1 的角色，res^10从单位矩阵开始做平方倍增才正确。我见过有人把res初始化成全 0，然后纳闷为什么结果全是 0，这就是没理解单位元的作用。

单位矩阵的构造很简单，对角线置 1，其余置 0。注意如果模数是 1，那1 % 1 = 0，单位矩阵会退化成全零矩阵，这时候所有结果都是 0，逻辑上仍然自洽，但要有心理准备，别以为是 bug。

3.4 矩阵快速幂在递推加速中的典型用法

十进制矩阵快速幂最常见的应用是加速线性递推。比如斐波那契数列，转移矩阵是 2x2 的，求第 n 项就是求转移矩阵的 n 次方再乘初始向量。当 n 以十进制字符串给出、长度上万时，普通矩阵快速幂没法做，十进制矩阵快速幂正好补上这个缺口。

构造转移矩阵的套路是固定的：把递推式写成状态向量，找出状态之间的线性关系，系数排成矩阵。比如f(n) = f(n-1) + f(n-2)，状态取[f(n), f(n-1)]，转移矩阵第一行是[1, 1]，第二行是[1, 0]。这个矩阵的 n-1 次方乘初始状态[f(1), f(0)]就得到[f(n), f(n-1)]。指数减一这一步别漏，很多人直接拿 n 次方去乘，结果整体错一位。

4. 实操过程：从零跑通一个完整例子

4.1 标量版完整代码与验证

先给一个可直接用的标量版实现，模数作为参数传入：

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll pow10mod(ll x, ll mod) { ll x2 = x * x % mod; ll x4 = x2 * x2 % mod; ll x8 = x4 * x4 % mod; return x8 * x2 % mod; } ll decPow(ll a, const string& n, ll mod) { a %= mod; ll pw[10]; pw[0] = 1 % mod; for (int i = 1; i <= 9; i++) pw[i] = pw[i-1] * a % mod; ll res = 1 % mod; size_t i = 0; while (i < n.size() && n[i] == '0') i++; for (; i < n.size(); i++) { res = pow10mod(res, mod); res = res * pw[n[i] - '0'] % mod; } return res; }

验证的时候我用了小指数对拍：随机生成a和较小的n，用普通快速幂算一遍，再用十进制版算一遍，两者必须相等。对拍跑了几万组没出问题，才敢往大指数上试。这个对拍习惯强烈建议保留，十进制快速幂的边界（前导零、指数为零、模数为 1）都靠它兜底。

4.2 矩阵版完整代码与对拍

矩阵版把上面的标量运算换成矩阵运算：

typedef vector<vector<ll>> Mat; ll MOD; Mat mul(const Mat& A, const Mat& B) { int k = A.size(); Mat C(k, vector<ll>(k, 0)); for (int i = 0; i < k; i++) for (int p = 0; p < k; p++) { if (!A[i][p]) continue; for (int j = 0; j < k; j++) C[i][j] = (C[i][j] + A[i][p] * B[p][j]) % MOD; } return C; } Mat matPow10(const Mat& A) { Mat A2 = mul(A, A); Mat A4 = mul(A2, A2); Mat A8 = mul(A4, A4); return mul(A8, A2); } Mat decMatPow(Mat M, const string& n) { int k = M.size(); Mat res(k, vector<ll>(k, 0)); for (int i = 0; i < k; i++) res[i][i] = 1 % MOD; Mat pw[10]; pw[0] = res; for (int i = 1; i <= 9; i++) pw[i] = mul(pw[i-1], M); size_t i = 0; while (i < n.size() && n[i] == '0') i++; for (; i < n.size(); i++) { res = matPow10(res); res = mul(res, pw[n[i] - '0']); } return res; }

对拍思路和标量版一样：小指数下用普通矩阵快速幂算，大指数下用十进制版，小指数部分两者必须一致。矩阵版对拍时我特意构造了非对称矩阵，确保乘法顺序错误能被抓出来。如果拿对称矩阵对拍，左乘右乘结果一样，就测不出顺序 bug，这个细节很关键。

4.3 一次真实的大指数运行记录

我拿斐波那契做了一次实测，指数是一个 5000 位的十进制数，模数取 1000000007，矩阵 2x2。运行时间在普通机器上大约是几十毫秒量级，主要开销在 5000 次矩阵十次方，每次四次 2x2 矩阵乘法，总共两万次小矩阵乘法，完全在可接受范围。如果把指数加到五万位，时间大致线性增长到几百毫秒，仍然能跑。

这里有个经验：矩阵阶数对时间的影响是立方的，指数位数是线性的。所以当矩阵阶数较大时，优先想办法降阶或者利用矩阵稀疏性，而不是纠结指数位数。我遇到过 10x10 的转移矩阵配一万位指数，那才是真的慢，后来通过重新设计状态把阶数降到 5，时间直接降了一个数量级。

5. 常见问题与排查技巧实录

5.1 结果整体偏移一位是怎么回事

这是最高频的问题。症状是算出来的结果和预期差一个指数位，比如求斐波那契第 n 项却得到了第 n-1 项或第 n+1 项。根因几乎都是转移矩阵的指数没处理好：要么忘了减一，要么初始向量取错。排查方法是拿 n=1、n=2 这种小值手算，和程序输出对比，定位偏移方向，然后调整指数或初始向量。我一般会在代码里写死几个小用例做断言，改代码时跑一遍，能挡住大部分低级错误。

5.2 模数为 1 或模数很大时的溢出

模数为 1 时所有结果都是 0，这是数学上正确的，不是 bug。模数很大（接近long long上限）时，两个小于模数的数相乘会溢出，这时候要么用__int128做中间类型，要么写快速乘。快速乘本身是 O(log) 的，会让整体常数上升，所以能用__int128就用，编译器支持的话一行搞定。

5.3 前导零导致的隐性性能问题

前导零不影响正确性，但会让程序多做若干轮无意义的十次方。指数串如果有一万个前导零，那就白跑一万轮矩阵十次方，时间直接翻倍。跳过前导零的代码就一行while，但很多人不写，因为小数据测不出来。我的习惯是在读入之后立刻做一次 trim，把前导零去掉再进主逻辑，这样主循环里不用再判断，代码也更干净。

5.4 字符串下标类型与越界

指数串长度可能超过int范围吗？理论上可以，但实际题目里几万到几十万位用int下标足够。不过用size_t更稳妥，避免和string::size()比较时出现符号问题。我踩过一次坑：用int i和n.size()比较，编译器警告有符号无符号比较，当时没在意，后来在某个边界上逻辑判断反了，查了半天。这种细节不值得省。

提示：主循环里n[i] - '0'之前确保i没有越界，跳过前导零的while之后要判断是否已经到串尾，全零串会直接走到尾，此时应返回单位元。

6. 几个值得记住的实操心得

第一，十进制快速幂的十次方一定要用平方倍增，不要写循环。这不是微优化，是指数位数上万时实打实的性能差距。第二，小幂表pw[0..9]的预处理几乎零成本，但能让主循环体极简，减少出错面。第三，矩阵版的乘法顺序是硬约束，res^10在左、M^d在右，拿非对称矩阵对拍是验证顺序的唯一可靠手段。第四，前导零 trim 和全零特判要写，别指望测试数据仁慈。

我个人在实际操作中的体会是，这套技巧的难点不在数学推导，那个恒等式五分钟就能想明白，难点全在工程细节：溢出、顺序、边界、初始化。把这些细节用对拍和小用例锁死，剩下的就是套模板。后面如果遇到指数以其他进制给出的变体，思路是一样的，把 10 换成对应进制、把十次方换成对应次方即可，核心恒等式不变。