如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）
title: 快速幂与矩阵快速幂
tags: 算法
推荐阅读和观看：
一 快速幂
我们用两道例题学习快速幂
pow(x, n)
实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:
-100.0 < x < 100.0 n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/powx-n 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
测试用例思考：
- 如果幂为负数，转换为正数再计算。但是
-2^31转为正数会溢出，需要使用long long来保存幂 0^0是1还是0?- 溢出情况如何处理？（和面试官沟通）
算法：快速幂 时间复杂度:O(logn)
迭代法：
class Solution {
public:
double myPow(double x, int n)
{
double ans = 1;
long long _pow = n;
if(n < 0)
{
x = 1 / x;
_pow *= -1;
}
while(_pow)
{
if(_pow & 1) ans *= x;
x *= x;
_pow >>= 1;
}
return ans;
}
};
递归法：
class Solution {
public:
double myPow(double x, int n)
{
long long _pow = n;
return _pow >= 0 ? FastPow(x, _pow) : 1.0 / FastPow(x, -_pow);
}
private:
double FastPow(double x, long long n)
{
if(n == 0)
return 1.0;
double y = FastPow(x, n / 2);
return n % 2 == 0 ? y * y : y * y * x;
}
};
超级次方
你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
示例 1：
输入：a = 2, b = [3]
输出：8
示例 2：
输入：a = 2, b = [1,0]
输出：1024
示例 3：
输入：a = 1, b = [4,3,3,8,5,2]
输出：1
示例 4：
输入：a = 2147483647, b = [2,0,0]
输出：1198
提示：
1 <= a <= 231 - 1 1 <= b.length <= 2000 0 <= b[i] <= 9 b 不含前导 0
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/super-pow 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int superPow(int a, vector<int>& b)
{
return Pow(a, b);
}
private:
const int MOD = 1337;
int Pow(int a, vector<int>& b)
{
if(b.empty()) return 1;
int back = b.back();
b.pop_back();
int p1 = fastPow(a, back);
int p2 = fastPow(Pow(a, b), 10);
return p1 * p2 % MOD;
}
int fastPow(int a, int b)
{
int ans = 1;
int base = a % MOD;
while(b)
{
if(b & 1) ans *= base, ans % MOD;
base *= base;
base %= MOD;
b >>= 1;
}
return ans % MOD;
}
};
二 矩阵快速幂
我们可以一道习题来引入矩阵快速幂：
斐波那契额数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
提示：
0 <= n <= 100
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
我们可以使用迭代法用 O(1) 的空间复杂度和 O(n) 的时间复杂度快速解决这个问题。但是我们可以使用矩阵快速幂的方法将时间复杂度降为 ：O(logn)
const int MOD = 1000000007;
const int N = 50;
struct mat
{
int m[N][N];
mat()
{
memset(m, 0, sizeof(m));
}
// 单位矩阵
void setUnitMat()
{
for (int i = 0; i < N; ++i)
m[i][i] = 1;
}
};
class Solution {
public:
int fib(int n)
{
if (n <= 1)
return n;
mat q;
q.m[0][0] = q.m[0][1] = q.m[1][0] = 1;
q.m[1][1] = 0;
mat ans = fastPow(q, n - 1);
return ans.m[0][0];
}
private:
const int n = 2;
mat&& fastPow(mat q, int n)
{
// ans 初始为单位矩阵
mat ans;
ans.setUnitMat();
while (n > 0)
{
if (n & 1)
ans = matrixMul(q, ans);
q = matrixMul(q, q);
n >>= 1;
}
return std::move(ans);
}
mat&& matrixMul(mat& q, mat& M)
{
mat ans;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
for (int k = 0; k < n; ++k)
{
ans.m[i][j] += q.m[i][k] * M.m[k][j] % MOD;
}
}
}
return std::move(ans);
}
};
其他例题：