快速幂

快速幂

例题:P1226 【模板】快速幂||取余运算 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

问题:对于一个数a,我们如何求出他的b次方?由于数可能比较大我们需要对结果对p取模

一般做法是a*a*a*…*a,一共有b个a相乘,如果b足够大,那么时间复杂度将为O(b),那么有没有什么方法可以快速运算呢?

例如:求2^10

我们需要先进行一个降幂操作,先使最终结果为sum,sum初始化为1

base 2 4 4 16 32 32
power 10 5 4 2 1 0
now 2^10 4^5 4^4 16^2 32^1 32^0
sum 1 1 1*4=4 4 4 4*32=128=2^10
times 0 1 1 2 3 3

由上表可以看出,当power为奇数的时候,我们需要让sum*=base,同时power-=1

当power==0时,此时sum就是最终结果

由例子可以看出,如果用暴力算法,需要运算10次,但是如果用快速幂只需要运算3次,故时间复杂度为O(logN)

如果我们要让结果对于p取模,根据取模的性质,我们只需每次操作的时候对sum和base取模即可

代码

1
2
3
4
5
6
7
8
9
10
11
long long fast(ll base, ll power, ll mod) {
    ll sum = 1;
    while (power > 0) {
        if (power % 2 == 1) {
            sum = (sum * base) % mod;
        }
        base = (base * base) % mod;
        power /= 2;
    }
    return sum % mod;
}

优化

对于2^10,我们可以发现:

10转化为二进制之后为:1010

第一次操作变为5 : 101 -> sum*=base

第二次操作变为2 : 10

第三次操作变为1 : 1 -> sum*=base

所以我们可以通过位运算对其进行简化

1
2
3
4
5
6
7
8
9
10
11
ll fast(ll base, ll power, ll mod) {
    ll sum = 1;
    while (power > 0) {
        if (power & 1) {
            sum = (sum * base) % mod;
        }
        base = (base * base) % mod;
        power >>= 1;
    }
    return sum % mod;
}

矩阵快速幂

首先你要会矩阵乘法,如果不会的话去CSDN - 专业开发者社区查,这里不多说,直接附上代码以及题目

(90条消息) 【详解】矩阵乘法__BOSS_的博客-CSDN博客_矩阵乘法

题目详情 - L1-048 矩阵A乘以B (pintia.cn)

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#include <string>
using namespace std;
typedef long long ll;
ll a[105][105], b[105][105];
ll c[105][105];
void mul(int r1, int r, int c2) {
    memset(c, 0, sizeof c);
    for (int i = 0; i < r1; i++) {
        for (int j = 0; j < c2; j++) {
            for (int k = 0; k < r; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
}
int main() {
    int r1, c1, r2, c2;
    cin >> r1 >> c1;
    for (int i = 0; i < r1; i++) {
        for (int j = 0; j < c1; j++) {
            cin >> a[i][j];
        }
    }
    cin >> r2 >> c2;
    if (c1 != r2) {
        printf("Error: %d != %d", c1, r2);
        return 0;
    }
    for (int i = 0; i < r2; i++) {
        for (int j = 0; j < c2; j++) {
            cin >> b[i][j];
        }
    }
    mul(r1, c1, c2);
    cout << r1 << ' ' << c2 << endl;
    for (int i = 0; i < r1; i++) {
        for (int j = 0; j < c2; j++) {
            if (j) {
                cout << ' ';
            }
            cout << c[i][j];
        }
        cout << endl;
    }
    return 0;
}

会了矩阵乘法之后,我们依旧用快速幂的思路来处理矩阵快速幂

这里附上题目链接P3390 【模板】矩阵快速幂 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1
2
3
4
5
6
7
8
9
10
void fast(ll base, ll power, ll mod) {
    单位矩阵 sum;
    while (power > 0) {
        if (power & 1) {
            矩阵乘法1:sum = sum * base;
        }
        矩阵乘法2:base = base * base;
        power >>= 1;
    }
}

我们只需往里面套入一个矩阵乘法即可

完整代码:

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll n, k;
ll a[105][105];
ll ans[105][105];
void get1() {
    ll c[105][105];
    memset(c, 0, sizeof c);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                c[i][j] += (ans[i][k] * a[k][j]) % mod;
                c[i][j] %= mod;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans[i][j] = c[i][j];
        }
    }
}
void get2() {
    ll c[105][105];
    memset(c, 0, sizeof c);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                c[i][j] += (a[i][k] * a[k][j]) % mod;
                c[i][j] %= mod;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            a[i][j] = c[i][j];
        }
    }
}
void fast(ll power) {
    while (power > 0) {
        if (power & 1) {
            get1();
        }
        get2();
        power >>= 1;
    }
}
int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        ans[i][i] = 1;
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    fast(k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j) {
                cout << ' ';
            }
            cout << ans[i][j];
        }
        cout << endl;
    }
    return 0;
}

矩阵快速幂与斐波那契数列

题目:P1962 斐波那契数列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

斐波那契数列应该都不陌生,它的每一项都是前两项之和,即:
$$
F_n = F_{n-1} + F_{n-2}\
其中F_0 = F_1 = 1
$$
我们将它写成
$$
\left[\begin{matrix}
F_n\
F_{n-1}
\end{matrix}\right]
$$
我们可以将其推到成:
$$
\left[\begin{matrix}
F_n\
F_{n-1}
\end{matrix}\right]=
\left[\begin{matrix}
1 & 1\
1 & 0
\end{matrix}\right]
*
\left[\begin{matrix}
F_{n-1}\
F_{n-2}
\end{matrix}\right]
$$
同理,我们不断对其进行拆分可得:
$$
\left[\begin{matrix}
F_n\
F_{n-1}
\end{matrix}\right]=
{\left[\begin{matrix}
1 & 1\
1 & 0
\end{matrix}\right]}^{n-1}
*
\left[\begin{matrix}
F_1\
F_0
\end{matrix}\right]
$$
结合以上可以得到完整代码:

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll n, k;
ll a[2][2];
ll ans[2][2];
ll b[2][1];
void get1() {
    ll c[105][105];
    memset(c, 0, sizeof c);
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                c[i][j] += (ans[i][k] * a[k][j]) % mod;
                c[i][j] %= mod;
            }
        }
    }
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            ans[i][j] = c[i][j];
        }
    }
}
void get2() {
    ll c[105][105];
    memset(c, 0, sizeof c);
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                c[i][j] += (a[i][k] * a[k][j]) % mod;
                c[i][j] %= mod;
            }
        }
    }
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            a[i][j] = c[i][j];
        }
    }
}
void fast(ll power) {
    while (power > 0) {
        if (power & 1) {
            get1();
        }
        get2();
        power >>= 1;
    }
}
ll c[2][2];
void mul() {
    memset(c, 0, sizeof c);
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 1; j++) {
            for (int k = 0; k < 2; k++) {
                c[i][j] += (ans[i][k] * b[k][j]) % mod;
                c[i][j] %= mod;
            }
        }
    }
}
int main() {
    cin >> n;
    a[0][0] = a[0][1] = a[1][0] = 1;
    ans[0][0] = ans[1][1] = 1;
    b[0][0] = 1;
    fast(n - 1);
    mul();
    cout << c[0][0];
    return 0;
}