首页 > 其他分享 >矩阵快速幂

矩阵快速幂

时间：2023-07-22 09:13:06浏览次数：75  
标签：end Matrix int 矩阵 times bmatrix 快速

矩阵乘法

限制条件 ：\(A\) 的列数等于 \(B\) 的行数

方法：

\[A \times B = C \Rightarrow C_{i,j} = \sum_{k=1}^{r} A_{i,k} \times B_{k,j} \]

举个栗子：

\[\begin{bmatrix} 1 & 2\end{bmatrix}\times \begin{bmatrix} 3 \\ 4\end{bmatrix}=\begin{bmatrix} 11 \end{bmatrix} \\ 1 \times 3 + 2 \times 4 = 11 \]

显然，矩阵乘法满足结合律，不满足交换律

我们还可以发现，若 \(A\) 是 \(n \times r\) 的矩阵， \(B\) 是 \(r \times m\) 的矩阵，那么 \(C\) 就是 \(n \times m\) 的矩阵

下面给出一个行数、列数都相等的矩阵乘法代码：

inline void Mul(int x[N][N], int y[N][N]) {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            ans[i][j] = 0;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = 1; k <= n; ++k)
                ans[i][j] += x[i][k] * y[k][j];
}

单位矩阵

主对角线上的元素都为 \(1\) ，其余元素都为 \(0\) 的 \(n\) 阶矩阵称作 \(n\) 阶单位矩阵

如图，这就是一个三阶单位矩阵：

\[\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \]

单位矩阵的一个性质：单位矩阵的任意次方都等于它本身。

在矩阵快速幂转移时，有时可以将其设为初始矩阵。

矩阵快速幂

限制条件：矩阵是一个长和宽相等的矩阵

定义：将方阵 \(A\) 自乘 \(n\) 次，记作 \(A^n\)。

因为矩阵乘法满足结合律，那么我们就可以利用快速幂的思想优化

P3390 【模板】矩阵快速幂

如代码所示：

#include <cstdio>
typedef long long ll;
using namespace std;
const ll Mod = 1e9 + 7;
const int N = 1e2 + 7;

template<int SIZE>
struct Matrix {
    ll a[SIZE][SIZE];
    int Row, Col;
    inline Matrix(int r = 0, int c = 0) {
        Row = r, Col = c;

        for (int i = 1; i <= Row; ++i)
            for (int j = 1; j <= Col; ++j)
                a[i][j] = 0;
    }
};

ll k;
int n;

inline Matrix<N> Mul(Matrix<N> &x, Matrix<N> &y) {
    Matrix<N> z(x.Row, y.Col);

    for (int k = 1; k <= x.Col; ++k)
        for (int i = 1; i <= x.Row; ++i)
            for (int j = 1; j <= y.Col; ++j)
                z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j] % Mod) % Mod;

    return z;
}

inline Matrix<N> Pow(Matrix<N> p, ll k) {
    Matrix<N> res = p, tmp = p;

    for (--k; k; tmp = Mul(tmp, tmp), k >>= 1)
        if (k & 1)
            res = Mul(res, tmp);

    return res;
}
signed main() {
    scanf("%d%lld", &n, &k);
    Matrix<N> ans(n, n);

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%lld", &ans.a[i][j]);

    ans = Pow(ans, k);

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            printf("%lld ", ans.a[i][j]);

        putchar('\n');
    }

    return 0;
}

P1962 斐波那契数列

我们设答案矩阵为 $ F_n = \begin{bmatrix} f_n & f_{n-1} \end{bmatrix}$ ，构建一个初始矩阵 \(A\) 与转移矩阵 \(B\) ，我们希望 \(F_n = F_{n-1} \times B = \begin{bmatrix} f_{n-1} & f_{n-2} \end{bmatrix} \times B\) 推出

因为 \(f_n = f_{n-1} \times 1 + f_{n-2} \times 1\) ，所以 \(B\) 的第一列为 \(\begin{bmatrix} 1 \\ 1 \end{bmatrix}\)

因为 \(f_{n-1} = f_{n-1} \times 1 + f_{n-2} \times 0\) ，所以 \(B\) 的第二列为 \(\begin{bmatrix} 1 \\ 0\end{bmatrix}\)

因此转移矩阵 \(B = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\)

因为 \(f_1 = f_2 =1\) ，所以我们设初始矩阵 \(A = F_2 = \begin{bmatrix} 1 & 1 \end{bmatrix}\)

综上所述，我们可以推出 \(F_n = A \times B^{n-2}\)

Code：

#include <cstdio>
typedef long long ll;
using namespace std;
const ll Mod = 1e9 + 7;
const int N = 7;

template<int SIZE>
struct Matrix {
    ll a[SIZE][SIZE];
    int Row, Col;
    inline Matrix(int r = 0, int c = 0) {
        Row = r, Col = c;

        for (int i = 1; i <= Row; ++i)
            for (int j = 1; j <= Col; ++j)
                a[i][j] = 0;
    }
};

ll n;

inline Matrix<N> Mul(Matrix<N> &x, Matrix<N> &y) {
    Matrix<N> z(x.Row, y.Col);

    for (int k = 1; k <= x.Col; ++k)
        for (int i = 1; i <= x.Row; ++i)
            for (int j = 1; j <= y.Col; ++j)
                z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j] % Mod) % Mod;

    return z;
}

inline Matrix<N> Pow(Matrix<N> p, ll k) {
    Matrix<N> res = p, tmp = p;

    for (--k; k; tmp = Mul(tmp, tmp), k >>= 1)
        if (k & 1)
            res = Mul(res, tmp);

    return res;
}
signed main() {
    scanf("%lld", &n);

    if (n <= 2) {
        putchar('1');
        return 0;
    }

    Matrix<N> A(1, 2), B(2, 2), ans(1, 2);
    A.a[1][1] = A.a[1][2] = 1;
    B.a[1][1] = B.a[1][2] = B.a[2][1] = 1, B.a[2][2] = 0;
    B = Pow(B, n - 2), ans = Mul(A, B);
    printf("%lld", ans.a[1][1]);
    return 0;
}

P1939 【模板】矩阵加速（数列）

我们设答案矩阵为 $ F_n = \begin{bmatrix} f_n & f_{n-1} & f_{n-2} \end{bmatrix}$ ，构建一个初始矩阵 \(A\) 与转移矩阵 \(B\) ，我们希望 \(F_n = F_{n-1} \times B = \begin{bmatrix} f_{n-1} & f_{n-2} & f_{n-3} \end{bmatrix} \times B\) 推出

因为 \(f_n = f_{n-1} \times 1 + f_{n-2} \times 0 + f_{n-3} \times 1\) ，所以 \(B\) 的第一列为 \(\begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}\)

因为 $f_{n-1} = f_{n-1} \times 1 + f_{n-2} \times 0 + f_{n-3} \times 0 $ ，所以 \(B\) 的第二列为 \(\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}\)

因为 $f_{n-2} = f_{n-1} \times 0 + f_{n-2} \times 1 + f_{n-3} \times 0 $ ，所以 \(B\) 的第二列为 \(\begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}\)

因此转移矩阵 \(B = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}\)

因为 \(f_1 = f_2 = f_3 = 1\) ，所以我们设初始矩阵 \(A = F_3 = \begin{bmatrix} 1 & 1 & 1 \end{bmatrix}\)

综上所述，我们可以推出 \(F_n = A \times B^{n-3}\)

Code：

#include <cstdio>
typedef long long ll;
using namespace std;
const ll Mod = 1e9 + 7;
const int N = 7;

template<int SIZE>
struct Matrix {
    ll a[SIZE][SIZE];
    int Row, Col;
    inline Matrix(int r = 0, int c = 0) {
        Row = r, Col = c;

        for (int i = 1; i <= Row; ++i)
            for (int j = 1; j <= Col; ++j)
                a[i][j] = 0;
    }
};

ll T, n;

inline Matrix<N> Mul(Matrix<N> &x, Matrix<N> &y) {
    Matrix<N> z(x.Row, y.Col);

    for (int k = 1; k <= x.Col; ++k)
        for (int i = 1; i <= x.Row; ++i)
            for (int j = 1; j <= y.Col; ++j)
                z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j] % Mod) % Mod;

    return z;
}

inline Matrix<N> Pow(Matrix<N> p, ll k) {
    Matrix<N> res = p, tmp = p;

    for (--k; k; tmp = Mul(tmp, tmp), k >>= 1)
        if (k & 1)
            res = Mul(res, tmp);

    return res;
}
signed main() {
    scanf("%lld", &T);

    for (; T; --T) {
        scanf("%lld", &n);

        if (n <= 3) {
            puts("1");
            continue;
        }

        Matrix<N> A(1, 3), B(3, 3), ans(1, 2);
        A.a[1][1] = 1, A.a[1][2] = 1, A.a[1][3] = 1;
        B.a[1][1] = 1, B.a[1][2] = 1, B.a[1][3] = 0;
        B.a[2][1] = 0, B.a[2][2] = 0, B.a[2][3] = 1;
        B.a[3][1] = 1, B.a[3][2] = 0, B.a[3][3] = 0;
        B = Pow(B, n - 3), ans = Mul(A, B);
        printf("%lld\n", ans.a[1][1]);
    }

    return 0;
}

标签：end,Matrix,int,矩阵,times,bmatrix,快速
From： https://www.cnblogs.com/wshcl/p/17572829.html

相关文章

  • 如何快速判断Oracle数据库是否运行缓慢
    查看过去一分钟数据库的响应时间SETLINESIZE200PAGESIZE50000COLBEGIN_TIMEFORMATA17COLEND_TIMEFORMATA17COLINST_IDFORMAT999COL"ResponseTime(msecs)"FORMAT999,999,999,999.99SELECTTO_CHAR(BEGIN_TIME,'DD-MON-YYYYHH24:MI')BEGIN......
  • matlab郭彦甫02基本操作与矩阵输入
    1.变量不声明    变量只能由数字 字母 _  组成        且不能以数字开头2.保留关键字  ans  运算结果 i  j  复数 inf  无穷∞eps  浮点相对精度  很小的数值NaN  非数字pi  圆周率iskeyword  查看matla......
  • Vue3 响应式全局对象json 动态绑定界面二 （方块矩阵样式）
    效果main.js//全局对象constglobalData=reactive({extTelMonitorData:[{title:'用户组一',list:[{groupID:"0",groupName:"AllUsers",......
  • 请享用美味的快速幂算法-通俗易懂版
    一、算法整体思路第1步按照最直接、最好理解的方式看，2的n次幂是n个2相乘，即有如下公式例如：第2步然而为了节省大量时间，通过简单的思考和严格数学推理，我们不难理解以下结论： 1.偶数幂的情况:通过幂函数运算法则，有2n=（2n/2）2，即有如下等式：例如24......
  • 矩阵求导攻略
    矩阵求导攻略定义与记号求导方法定义法求导逐分量求导矩阵微分求导矩阵微分求导......
  • 在CSDN中如何快速转载文章
    问题：在CSDN中如何快速转载文章解决步骤：1.在CSDN中找到想要转载的文章，右击点击"检查"（或者快捷键F12）出现以下界面（图下图右侧所示）2.按住Ctrl+F快捷键，寻找"article_content"3.选中divid="article_content"那一行，如下图所示右击"Copy"—"CopyHTML"4.打开CSDN，依次点击......
  • C++数值计算——矩阵类的实现（一）
    本系列博客将利用C++实现一系列数值算法。数值算法离不开矩阵，但是C++并未自带矩阵这一对象，直接使用数组又会带来诸多不便，因此我们需要做一些预备工作————编写一个矩阵类，实现矩阵的基本功能。一般来说，读者可以直接使用Eigen库进行矩阵计算，从头开始造轮子仅仅是为了满足笔者个人......
  • windows mysql快速导入数据库文件
    Windows下快速导入MySQL数据库文件在开发和维护项目时，我们通常需要将数据库中的数据导入到本地进行分析和测试。对于MySQL数据库，我们可以通过一些简单的步骤来快速导入数据库文件。在本文中，我们将介绍在Windows环境下如何实现快速导入数据库文件的方法。步骤一：安装MySQL首先，我们......
  • 【随手记录】docker swarm集群快速创建
    创建集群主节点：dockerswarminit--advertise-addr=192.168.31.184#advertise-addr主节点IP#同时默认会创建一个ignress网络，这个不能删，如果容器端口映射到外面，则容器会默认加入到这个ignress网络里,如果删除了，存在需要对外开放端口的镜像则会报错找不到ignress网络#即时手动do......
  • Android opencv Mat 创建单位矩阵
    AndroidOpenCVMat创建单位矩阵在计算机视觉和图像处理中，矩阵是一个非常重要的概念。矩阵可以表示图像的像素值、进行图像变换、计算特征向量和特征值等。Android平台上，OpenCV是一个强大的图像处理库，提供了许多矩阵操作的函数和工具。本文将介绍如何使用OpenCV在Android上创建单......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99