★ FEATURED ARTICLE 1. 从一道卡了三天三夜的题说起十进制快速幂和十进制矩阵快速幂这两个词放在一起很多人第一反应是“二进制快速幂我熟啊十进制又是什么鬼”。我第一次碰到这个概念是在做一道指数大到离谱的递推题时——指数给了整整一千位十进制数字用二进制快速幂得先把这个十进制大数转成二进制转换过程本身就要处理大数除法写起来又臭又长常数还大。当时卡了三天后来被一位搞竞赛的老哥点了一句“你为什么不直接按十进制位来拆指数”才恍然大悟。这篇内容就是把这套思路彻底讲透。它解决的核心问题是当指数以十进制字符串形式给出、长度达到10^5甚至更大时如何在不做大数进制转换的前提下高效计算 a^n mod p 以及矩阵的 M^n mod p。适合已经掌握二进制快速幂、会写矩阵乘法、正在啃大指数递推或计数类问题的读者。哪怕你只是听说过快速幂跟着下面的推导走也能把十进制版本吃下来因为它的本质和二进制版本是同一套思想只是“进位基”从2换成了10。先说清楚它为什么值得单独拎出来讲。二进制快速幂的复杂度是 O(log n)这里的 log 是以2为底十进制快速幂是 O(十进制位数 × 10)看起来多了个常数10但省掉了“把十进制大数转成二进制”这一整块开销。在指数有十万位十进制数字的场景下这个省法直接把代码复杂度和常数都压下去了。矩阵版本同理只是每次乘的是矩阵而不是标量预处理的幂次表从“a 的 2^k 次”变成“M 的 10^k 次”。2. 核心思路拆解为什么按十进制位拆是成立的2.1 从二进制快速幂的本质说起二进制快速幂之所以成立靠的是指数的二进制展开n Σ b_i · 2^i于是 a^n Π (a^(2^i))^(b_i)。我们预处理出 a^1, a^2, a^4, a^8, …然后根据 n 的每一位决定乘不乘。整个过程的关键在于“底数不断平方、指数不断右移”这个循环不变量。把这个思想抽象出来只要能把指数 n 表示成某个进位基 B 的多项式就能做“B 进制快速幂”。二进制只是 B2 的特例十进制就是 B10。所以十进制快速幂不是什么新算法而是同一框架换了个基。理解这一点后面所有推导都是顺水推舟。2.2 十进制展开的递推形式设指数 n 的十进制表示为 d_1 d_2 … d_Ld_1 是最高位。从高位往低位扫描维护一个当前结果。递推关系是处理完前 i 位后的指数值 N_i N_{i-1} × 10 d_i对应到幂运算上a^(N_i) (a^(N_{i-1}))^10 × a^(d_i)这就是十进制快速幂的全部核心。每读一位先把当前累积结果自乘10次也就是取10次方再乘上 a 的该位数字次方。由于每一位数字只有0到9十种可能a^0 到 a^9 可以提前打表取10次方也可以用“平方再平方再乘”或者直接循环10次。对比二进制版本二进制是“平方一次、看一位”十进制是“取10次方、看一位”。取10次方的开销是固定的约4次乘法a^2, a^4, a^8, a^8·a^2所以整体复杂度是 O(L · log10)L 是十进制位数。当 L 达到10^5时这个量级完全可以接受。2.3 为什么不用“先转二进制”有人会问我先把十进制大数转成二进制再用普通快速幂不行吗行但代价是大数转二进制需要对整个十进制串反复做除以2的运算每次除法 O(L)总共 O(L^2) 次基本操作L10^5 时就是10^10量级直接超时。而十进制快速幂是 O(L) 次乘法差距是数量级的。这就是“按原进制处理”的价值——不要在算法入口处做不必要的信息转换让数据的天然表示直接服务于算法结构。2.4 矩阵版本的特殊性矩阵快速幂和标量快速幂的唯一区别是乘法不满足交换律但这不影响十进制展开的正确性因为递推式 a^(N_i) (a^(N_{i-1}))^10 × a^(d_i) 里两个因子都是同一个矩阵 M 的幂而 M 的任意两个幂是可交换的M^p · M^q M^q · M^p M^(pq)。所以顺序怎么写都对。真正需要注意的是矩阵乘法的常数一个 k×k 矩阵乘法是 O(k^3)取10次方约4次矩阵乘法每位数字再乘一次预处理的 M^d所以每位约5次矩阵乘法。L10^5、k2 时大约是 5×10^5 × 8 4×10^6 次基本运算完全跑得动。预处理表也不同标量版预处理 a^0…a^9矩阵版预处理 M^0…M^9其中 M^0 是单位矩阵。这一步千万别写成全零矩阵否则后面全错。3. 标量十进制快速幂的完整实现与细节3.1 预处理幂次表先把 a^0 到 a^9 打出来。a^0 1模 p 意义下a^1 a % p之后逐个累乘。这一步 O(10) 次乘法可以忽略不计。注意每一步都要取模防止中间结果溢出。如果 p 接近 int 上限两个小于 p 的数相乘可能爆 long long需要用 __int128 或者先转成更大类型再取模。long long pw[10]; pw[0] 1 % p; for (int i 1; i 10; i) pw[i] pw[i-1] * a % p;这里有个小坑如果 p 1那么所有结果都是0pw[0] 应该是 1 % 1 0代码里写 1 % p 就自动处理了。别小看这个边界我见过有人写 pw[0] 1 然后 p1 时输出1WA得莫名其妙。3.2 主循环逐位扫描从字符串最高位开始扫维护结果 res。初始 res 1对应空指数的 a^0。每读一位 d对 res 取10次方res res^10 mod p再乘上 pw[d]res res * pw[d] mod p取10次方的写法有讲究。最直白的是循环10次乘10次乘法优化一点用平方res2 resres, res4 res2res2, res8 res4res4, res10 res8res2共4次乘法。位数多的时候这4次和10次的差距会被放大建议用平方版。long long res 1 % p; for (char c : s) { int d c - 0; // res res^10 long long r2 res * res % p; long long r4 r2 * r2 % p; long long r8 r4 * r4 % p; res r8 * r2 % p; // 乘上 a^d res res * pw[d] % p; }3.3 一个容易忽略的细节前导零如果指数串有前导零比如 007按上面的流程走res 初始1读0res 1^10 * a^0 1读0还是1读7res 1^10 * a^7 a^7。结果正确。所以前导零不影响正确性只是多做了几次无用功。如果在意常数可以先跳过前导零但没必要因为 L 的量级本来就允许。3.4 指数为0和底数为0的边界指数串是 0 时循环读一位0res 1^10 * a^0 1正确a^0 1约定 0^0 1 时也对。底数 a 0 且指数大于0时pw[1..9] 全是0res 最终为0正确。底数 a 0 且指数为0时按约定输出1。这些边界在竞赛题里经常作为 hack 点写的时候顺手测一下。4. 十进制矩阵快速幂把标量逻辑平移过来4.1 矩阵乘法的封装先写一个干净的矩阵乘法函数。以 2×2 为例但建议写成模板或固定大小循环方便扩展到 k×k。核心是三重循环加取模注意累加时用 long long 甚至 __int128 防溢出。struct Mat { long long v[2][2]; Mat() { memset(v, 0, sizeof(v)); } }; Mat mul(const Mat A, const Mat B, long long p) { Mat C; for (int i 0; i 2; i) for (int k 0; k 2; k) { if (A.v[i][k] 0) continue; for (int j 0; j 2; j) C.v[i][j] (C.v[i][j] A.v[i][k] * B.v[k][j]) % p; } return C; }那个if (A.v[i][k] 0) continue是稀疏优化矩阵里零多的时候能省不少乘法。递推矩阵通常比较稠密但加上也无害。4.2 预处理 M^0 到 M^9M^0 是单位矩阵M^1 M之后逐个乘 M。这里必须用矩阵乘法不能像标量那样直接累乘数值。Mat pw[10]; pw[0] identity(); // 单位矩阵 for (int i 1; i 10; i) pw[i] mul(pw[i-1], M, p);单位矩阵的构造主对角线为 1 % p其余为0。同样注意 p1 时对角线是0。4.3 主循环的矩阵版逻辑和标量完全一致只是每次“取10次方”变成矩阵的10次方“乘 pw[d]”变成矩阵乘。Mat res identity(); for (char c : s) { int d c - 0; Mat r2 mul(res, res, p); Mat r4 mul(r2, r2, p); Mat r8 mul(r4, r4, p); res mul(r8, r2, p); // res^10 res mul(res, pw[d], p); }注意矩阵乘法顺序res^10 在前pw[d] 在后因为递推式是 (M^(N_{i-1}))^10 × M^(d_i)。虽然 M 的幂可交换但养成按公式写的习惯换到不可交换的场景比如带仿射变换的矩阵就不会出错。4.4 复杂度与常数优化每位数字约5次矩阵乘法4次算10次方 1次乘 pw[d]。k×k 矩阵一次乘法 k^3 次乘加。L10^5、k2 时约 4×10^6 次乘加k3 时约 1.35×10^7都在一秒内。如果 k 更大或者 L 更长可以考虑把“取10次方”改成预计算 res^2, res^4, res^8 后组合已经是4次了很难再降或者用更快的矩阵乘法Strassen 在小矩阵上不划算别折腾。一个实测有效的优化如果某一位 d0乘 pw[0] 是单位矩阵可以跳过那次乘法。指数串里0的比例约1/10能省一点。5. 常见问题与排查实录5.1 结果全错但小数据对最常见的原因是取模位置不对。比如预处理 pw 时忘了取模或者矩阵乘法累加后忘了取模。小数据时数值不溢出结果看着对数据一大就崩。排查方法把所有中间结果都打印出来和暴力版对拍。我习惯写一个 O(n) 的暴力快速幂指数小的时候直接循环乘随机生成小指数对拍能快速定位是预处理错还是主循环错。5.2 矩阵版答案偏移一位十有八九是 M^0 写成了全零矩阵或者主循环里 res 初始值写成了 M 而不是单位矩阵。记住空指数对应单位矩阵就像标量里空指数对应1。这个类比能帮你记住所有初始值。5.3 大指数下超时检查是不是把“取10次方”写成了循环10次乘法。10次和4次的差距在 L10^5 时是6×10^5 次乘法矩阵版就是6×10^5 × k^3k3 时约1.6×10^7可能刚好卡在时限边缘。改成平方组合版立刻降下来。5.4 溢出问题p 接近 10^9 时两个小于 p 的数相乘接近 10^18long long 上限约9.2×10^18单次乘法不溢出但矩阵乘法里累加 k 次就可能溢出。k2 时累加2次约2×10^18安全k3 时3×10^18仍安全k 再大就要用 __int128 或者每次累加后立即取模。标量版单次乘法安全但如果你写的是 res res * res % p 连续几次每次都有取模没问题。5.5 常见问题速查表现象可能原因排查动作小数据对、大数据错中间结果未取模导致溢出检查每步乘法后是否取模矩阵版结果偏移M^0 非单位矩阵或 res 初值错确认单位矩阵构造和 res 初始化大指数超时取10次方用了循环10次改为平方组合的4次乘法答案差一个因子主循环顺序颠倒确认先取10次方再乘 pw[d]p1 时输出1pw[0] 或单位矩阵未对p取模所有初值统一 1 % p6. 实操心得与几个容易踩的坑第一个心得先把标量版写对再上矩阵。标量版的逻辑和矩阵版一模一样但调试成本低得多。标量版对拍了矩阵版只需要检查矩阵乘法和单位矩阵两处排查范围立刻缩小。第二个心得指数串用 string 读别用 long long。题目给十万位十进制数用任何整数类型都存不下。读进来直接扫字符连转数字数组都省了。第三个心得预处理表的大小固定为10不要动态开。有人为了“通用”写成按最大数字开表结果最大数字是9表长10反而容易越界。固定10最稳。第四个心得矩阵乘法里那个稀疏判断值得加。递推矩阵经常有零元素加上if (A.v[i][k] 0) continue在 k3 以上时能省20%到30%的时间代码只多一行。第五个心得对拍时构造指数为0、1、9、10、11、99、100 这几个边界。这几个能覆盖“单位矩阵”“个位数”“进位”“多位进位”所有情况比随机对拍更快发现问题。最后分享一个扩展方向这套框架可以推广到任意 B 进制快速幂把10换成B预处理表开到B取B次方用平方组合。B2 就是经典快速幂B10 是十进制版B1000 在某些场景下能进一步减少位数。理解了“按进位基展开”这个本质换基只是改两个常数的事。我在实际使用中发现凡是指数以某种进制字符串形式给出的题优先考虑按该进制直接处理往往比转换进制更省事也更稳。
阅读完成 · 觉得有帮助？
