数学(快速幂).pdfVIP

数学 ——Shine_Sky - 13,快速幂 先有一个问题给出n , k 求 ,如果k 很小我们完全可以用一个for 循环得出答案， 但是往往OI 中要求幂的题出题人都不会良心，所以我们得学习快速幂。 虽然C++ 中的cmath 库中有个pow 函数可以快速求出 但是其缺陷是不能及时取 mo 所以而且又返回double 所以难以储存为我们想要的，所以我们不提起它 现在相求1001000mod1000007 如果我们用for 循环那么时间复杂度是O(k) = O(1000) 的虽然这不大，但是接下来看快速幂就知道这是有多慢了 3 5 6 7 8 9 我们将k 转换为二进制就是1111101000 即1000 = 2 + 2 + 2 + 2 + 2 + 2 ; 由于同底数幂的运算我们可以把1001000 转换为 10023 × 10025 × 10026 × 10027 × 10028 × 10029 这样我们可以发现我们只要运算 次也就是说6 次，怎么实现得到每一个小数的值 2 呢，for 循环肯定不能考虑我们看到二进制就可以想到位运算，我们用k1 判断k 的二 进制最后一位是不是 1，是则ans *= x 如果不是就不作为然后再将x *= x 并k 右移一 位伪代码如下： Int ans = 0; while(k 非0) { If(k 最后一位是1) ans *= x; X *= x; k 右移一位 } - 14，矩阵乘法 数学上的东西（这几章都关于数学，这是个废话），是用来计算两个数矩形的积的 其中公式为我们现在有两个矩阵A , B 如果要求他们的积，则必须满足A 的第一行与 B 的第一列相同则有积C 各个位置值为 ; 例子：无 - 13 + 14 矩阵快速幂 将上述两个结合起来，我们只要把快速幂的乘法更换一下改为一个函数，这个函 数是用来求矩阵乘法的，这都不是很困难，但是我们要返回一个2 维数组，我们用一 的方法很难做到，所以要用不一般的，我们定义一个结构体JX 储存一个矩阵，再将快 速幂和矩阵乘法的返回值改为JX 就好了，下见Code(为了容易截图，压了行)