再次温习矩阵快速幂的一些思路

算法重温
字数统计: 1.3k字   |   阅读时长: 6分

写在前面

因为之前4月份打了将近一个月的个人赛，有些以前学习过的算法已经忘了，所以重新再温习一遍。

关于矩阵快速幂

矩阵快速幂就是把整数变成矩阵用快速幂来算其次方，比如$A^{n-2}$，其中$A=\begin{Bmatrix}
1 & 1\\
1& 0
\end{Bmatrix}$,像这样的就是矩阵快速幂。

矩阵快速幂

矩阵的一些名词定义

  • $n$阶矩阵：$\begin{Bmatrix}
    1 & 1\\
    1& 0
    \end{Bmatrix}$，这就是一个$2∗2$的矩阵，也叫$2$阶矩阵。

  • 行向量：只有一行的矩阵，也叫行矩阵，$(a1,a2,…,an)$这就是一个行向量。

  • 列向量：只有一列的矩阵，也叫列矩阵，$\begin{Bmatrix}
    a_{1}\\
    a_{2}\\
    a_{3}\\
    …\\
    a_{n}
    \end{Bmatrix}$，这就是一个列向量。

矩阵的相关运算

矩阵加法：

设有两个$m*n$的矩阵，$A=(a_{ij})$，$B=(b_{ij})$，那么矩阵$A$和$B$的和记做$A+B$。也就是对应相加重新构成的一个矩阵。这里要注意的是，只有当两个矩阵是同型矩阵（也就是行数相等列数也相等）时，这两个矩阵才能进行加法运算。

矩阵乘法：

就是对应的第一个矩阵的第一行的第一个数乘以第二个矩阵的第一列的第一个数；
第一个矩阵的第一行的第二个数乘以第二个矩阵的第一列的第二个数。总结来说就是第一个矩阵的每一行去乘以对应的第二个矩阵的每一列。

PS1：剩下的许多关于矩阵的知识可以看这篇博客：https://blog.csdn.net/nuoyanli/article/details/105314274

PS2：视频讲解可以看这个视频：https://www.bilibili.com/video/BV1gx41127d7?p=1

矩阵快速幂的模板及例题

矩阵快速幂的模板

首先先给出矩阵乘法的模板，这里以51nod-1137为例

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
#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 1010;
const int inf = 0x3f3f3f3f;
using namespace std;
int m1[maxx][maxx], m2[maxx][maxx], m[maxx][maxx];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    memset(m, 0, sizeof(m));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> m1[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> m2[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                m[i][j] += m1[i][k] * m2[k][j];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cout << m[i][j] << " ";
        cout << endl;
    }
    return 0;
}

给出矩阵快速幂的模板，这里以51nod-1113为例

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
#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 110;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define mod(x) ((x) % mod)
using namespace std;
int n;
struct mat
{
    int m[maxx][maxx];
} unit; //矩阵
mat operator*(mat a, mat b)
{ //重载矩阵乘法
    mat res;
    ll x; //可能爆int
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            x = 0;
            for (int k = 0; k < n; k++)
                x += mod((ll)a.m[i][k] * b.m[k][j]);
            res.m[i][j] = mod(x);
        }
    return res;
}
void init_unit()
{ //定义单位矩阵
    for (int i = 0; i < maxx; i++)
        unit.m[i][i] = 1;
    return;
}
mat pow_mat(mat a, ll n)
{ //矩阵快速幂,跟快速幂形式上差不多
    mat res = unit;
    while (n)
    {
        if (n & 1)
            res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll x;
    init_unit();
    while (cin >> n >> x)
    {
        mat a;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> a.m[i][j];
        a = pow_mat(a, x);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                if (j + 1 == n)
                    cout << a.m[i][j] << endl;
                else
                    cout << a.m[i][j] << " ";
            }
    }
    return 0;
}

例题：POJ-3070

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 <algorithm>
#include <functional>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
typedef long long ll;
const int maxx = 110;
const int inf = 0x3f3f3f3f;
const int mod = 1e4;
using namespace std;
int n = 2;
struct mat
{
    int m[maxx][maxx];
} unit;
mat operator*(mat a, mat b)
{
    mat res;
    ll x;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            x = 0;
            for (int k = 0; k < n; k++)
                x = (x + a.m[i][k] * b.m[k][j]) % mod;
            res.m[i][j] = x % mod;
        }
    return res;
}
void init_unit()
{
    for (int i = 0; i < maxx; i++)
        unit.m[i][i] = 1;
    return;
}
mat pow_mat(mat a, ll n)
{
    mat res = unit;
    while (n)
    {
        if (n & 1)
            res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll x;
    init_unit();
    while (cin >> x && x != -1)
    {
        mat a;
        a.m[0][0] = 1;
        a.m[0][1] = 1;
        a.m[1][0] = 1;
        a.m[1][1] = 0;
        a = pow_mat(a, x);
        cout << a.m[0][1] << endl;
    }
    return 0;
}

赏

×

纯属好玩

扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:再次温习矩阵快速幂的一些思路

文章作者:Stephencurry6666

发布时间:2020年05月19日 - 11时33分

最后更新:2020年05月19日 - 12时00分

原始链接:https://stephencurry6666.github.io/2020/05/19/%E5%86%8D%E6%AC%A1%E6%B8%A9%E4%B9%A0%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82%E7%9A%84%E4%B8%80%E4%BA%9B%E6%80%9D%E8%B7%AF/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 写在前面
  2. 2. 关于矩阵快速幂
  3. 3. 矩阵快速幂
    1. 3.1. 矩阵的一些名词定义
    2. 3.2. 矩阵的相关运算
  4. 4. 矩阵快速幂的模板及例题
    1. 4.1. 矩阵快速幂的模板
    2. 4.2. 例题：POJ-3070
,
字数统计：87.6k 载入天数...载入时分秒...