算法专题（7）-高精度算法与快速幂

高精度算法与快速幂

概述：

有的时候，数字会大到连long long（或int64）都不能承受的程度。这时，我们可以用数组来模拟大数的各种运算。该模拟方法即为高精度算法。

快速幂即为求解形如aⁿ的快速算法。

1.知识点梳理：

Ø 高精度的存储

高精度存储采用数组存储每一位的值，并记录数组的长度和正负性。一般来讲，数组的下标越小，对应的整数的位越小。对于一个高精度整数n，用十进制计数后，其位数为k，每一位的值分别为a[0]~a[k-1]，

Ø 高精度的四则运算

加法：模拟整数加法的过程，从低位到高位逐位相加，判断进位即可。需要注意更新结果的位数，另外要注意负数情况。如果都为负，则相加后取负；如果只一个为负数，将其变成两数相减的形式。

减法：模拟整数减法的过程，从高位到低位逐位相减，不足从高位补即可。要更新结果的位数，另外要注意结果为负数。

乘法：模拟整数乘法的过程，依次两两相乘即可。对于10000进制存储的压位高精度，要注意在中间步骤进位，防止溢出。

除法：模拟整数除法的过程，从高位到低位逐位相除，最后可得出商和余数。在每一位相除的过程中，需要枚举该位的商。对于10000进制存储的压位高精度，直接枚举复杂度高，一般采用二分枚举。不过在NOIP中，高精度除法应用较少。

Ø 快速幂

一般求解aⁿ时，用依次相乘的方法即可，复杂度为O(n)，但实际上，如果记录a⁰, a¹, a², a⁴, a⁸, ... , 的值（其中），就可快速求解aⁿ，复杂度为O(log n)。如果直接求解，还需要用到高精度，复杂度会比较高。不过一般涉及到这类问题的题目，都要求计算出的解除以p取余数的结果。直接对每一步的计算结果取余数，就可以不用高精度计算。当然，快速幂的计算不仅仅限于计算一个值的幂，还可以用于递推下的矩阵计算。

2.重难点分析：

u高精度算法中的正负号问题、升位与降位问题在运算中需要特别注意。

u高精度算法在编写是容易出错，最好能准备一套模板。

u快速幂求解时，应按照题目要求，看是否加入高精度。

3.例题解析：

例题2-1：斐波那契数列第n项的值

【问题描述】计算斐波那契数列第n (n≤10¹⁰) 项的值。由于这个值会很大，只要计算其除以p的余数即可。

【分析】此题由于n非常大，直接一步步递推肯定超时，因此，需要利用快速幂的思想。已知斐波那契数列为

对其进行加强，可得当k≥3时，

原问题就变为求解矩阵的k-1次幂，可以参考数值快速幂的方法求解矩阵快速幂，具体就不做赘述。对于矩阵乘法不了解的同学，可查找任何关于矩阵乘法的资料。

例题2-2：2^k进制数（NOIP2006）

【问题描述】设r是个2^k进制数，并满足以下条件：

（1）r至少是个2位的2^k进制数。

（2）作为2^k进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。

（3）将r转换为2进制数q后，则q的总位数不超过w。

在这里，正整数k (1≤k≤9) 和w (k<w≤30000) 是事先给定的。

问：满足上述条件的不同的r共有多少个？

我们再从另一角度作些解释：设S是长度为w 的01字符串（即字符串S由w个“0”或“1”组成），S对应于上述条件（3）中的q。将S从右起划分为若干个长度为k 的段，每段对应一位2^k进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2^k 进制数r。

例：设k=3，w=7。则r是个八进制数（2³=8）。由于w=7，长度为7的01字符串按3位一段分，可分为3段（即1，3，3，左边第一段只有一个二进制位），则满足条件的八进制数有：

2位数：高位为1：6个（即12，13，14，15，16，17），高位为2：5个，…，高位为6：1个（即67）。共6+5+…+1=21个。

3位数：高位只能是1，第2位为2：5个（即123，124，125，126，127），第2位为3：4个，…，第2位为6：1个（即167）。共5+4+…+1=15个。

所以，满足要求的r共有36个。

【输入】

k W

【输出】

仅一行，为所求的计算结果，即满足条件的不同的r的个数（用十进制数表示），要求最高位不得为0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。

（提示：作为结果的正整数可能很大，但不会超过200位）

【分析】本题为组合数学与高精度的结合题。先分析题目，题目中要求r除最后一位外，每一位严格小于它右边相邻的那位。如果已知r的位数为x，题目就转化为组合数学问题（即在2^k-1个数中，选取x个数）解的个数为

。另外，当位数最多时，需要考虑特殊情况。由于r转换为2进制后总位数不能超过w。那么r的最多位数为

，当位数最多的情况下，最高位的最大值为

。综上，本题的解为：

，约定，当i>j时，

。

本题需要先预处理组合数，用加法递推公式预处理即可，复杂度为O(2^2k)。求解时，对位数进行讨论，当取到位数最多的情况时，需考虑最高位的值，复杂度为O(w/k+2^k)。整体复杂度为O(w/k+2^2k)。另外，本题需要用大整数高精度算法。

对于组合数学学的不够高的同学，本题是还可以用递推（或动态规划）来求解。先分析题目，题目要求r除最后一位外，每一位严格小于最后一位。那么，我们可以从最后一位开始，逐渐递推高位。所要保存的值为，当位数为i，最高位为j时，所含有的r的个数。具体如下：

设f[i][j]为当一个i位2^k进制数最高位为j时所含有r的个数。由于题目中说，r除最后一位外，每一位严格小于最后一位，那么，递推公式如下：

本题中要求r转化为二进制数q后，其位数不超过w。又由于r每一位其实相当于二进制的k位。那么，r的最多位数为

，最高位的最大值为

，最后的解为：

至于为什么只要枚举最多位数的最高位就可以计算，因为最高位为零的情况包含了位数少于最多位数的所有可能情况了。

如果不加优化，枚举i时需要O(w/k)次枚举，枚举j时，需要O(2^k)次枚举，计算时，需要最多2^k次计算，整体复杂度为O(w/k*2^2k)，会超时。因此，在原递推公式的基础上，需要做一下优化。

已知当i≥1, j≤2^k-1时，

复杂度降为O(w/k*2^k)，由于本题用到高精度，也有一定的超时风险。