快速幂和矩阵快速幂详解+模板

136 阅读 0 评论 90 点赞

我是靠谱客的博主专一睫毛，这篇文章主要介绍快速幂和矩阵快速幂详解+模板，现在分享给大家，希望可以做个参考。

`1.快速幂`

一般的，我们都知道求 $large 2^3$ 只需要连续乘3次2就能得到，那么 $large 2^{13}$ 等于多少呢？其实这个一很简单，不就是13个2相乘吗，连续乘13次2就行了。那么 $large 2^{100}$ , $large 2^{1000}$ 呢? 是不是要连续乘100次、1000次，我们将这类问题归结为求 $large a^b$ 。那么当b很大的时候，是很浪费时间的，往往会造成超时，那有没有更快的计算方法呢？当然了，接下来就是这篇文章的重点:快速幂。

我们以b=13为例，将b表示为二进制：
$bg_white large b=13=[1101]_2=2^3times 1+2^2times 1+2^1times 0+2^0times1$
那么:
$\a^b=a^{2^3times 1+2^2times 1+2^1times 0+2^0times1}\{ }quad=a^{2^3}times a^{2^1}times a^{2^0}$
那么我们观察只要b的2进制的第i位为1，就乘上(这个值可以在循环中得到)。
大家可以发现，这样计算要比普通的连乘计算要简单快速的多，如果你要计算，连乘要计算10000次，而快速幂大概要计算次。这就是快速幂算法，它将幂次运算由O(n)简化到了O().
快速幂充分利用了二进制的特点(非0即1)，把十进制转化成二进制后再展开，对于每一位的当前结果要么乘要么不乘，把原本n次的循环变成了n的二进制位数的循环。

推广到 $large a^b$ ：
令 $b=p_0^{2^k}+p_1^{2^{k-1}}+...+p_k^{2^0}$ ;
则 $a^b=a^{p_0^{2^k}+p_1^{2^{k-1}}+...+p_k^{2^0}}$ .

代码:

复制代码

1
2
3
4
5
6
7
8
9
10
11
typedef long long ll;
ll _power(ll a, int b, int p) { //计算(a^b)%p;
    ll ans = 1;
    while (b) {
        if (b & 1) //等价于b%2，判断b的奇偶性
            ans = ans * a % p; //如果为奇数，证明该位为1，需要乘上a
        a = a * a % p; //计算a^(2^i)
        b >>= 1; //等价于b/=2;
    }
    return ans;
}

快速幂取模算法原理:(a * b) % p = ((a % p) * (b % p)) % p.
如果不需要取模，把取模运算去了就行了。

`2.矩阵快速幂`

矩阵快速幂和上面的快速幂原理是一样的，不同的是上面的那个是数，这个是矩阵而已。
直接上代码:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef long long ll;
const int mod = 1e9 + 7;
const int MAXN = 10005;//矩阵的大小
struct Mat {
    ll m[MAXN][MAXN];
}ans, a;//ans为结果矩阵，a为输入矩阵
Mat Mul(Mat a, Mat b, int n) {//计算矩阵a乘矩阵b，n为矩阵的大小
    Mat c;//临时矩阵c
    memset(c.m, 0, sizeof(c.m));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                c.m[i][j] = (c.m[i][j] + (a.m[i][k] * b.m[k][j]) % mod) % mod;
    return c;
}
Mat _power(Mat a, int b, int n) {//计算a^b，n为矩阵的大小
    for (int i = 1; i <= n; i++)//构造单位矩阵
        ans[i][i] = 1;
    while (b) {
        if (b & 1)
            ans = Mul(ans, a, n);
        a = Mul(a, a, n);
        b >>= 1;
    }
    return ans;
}