专栏首页CSDN旧文疯子的算法总结(五) 矩阵乘法 (矩阵快速幂)

疯子的算法总结(五) 矩阵乘法 (矩阵快速幂)

学过线性代数的都知道矩阵的乘法,矩阵乘法条件第为一个矩阵的行数等与第二个矩阵的列数,乘法为第一个矩阵的第一行乘以第二个矩阵的第一列的对应元素的和作为结果矩阵的第一行第一列的元素。(详解参见线性代数) 于是我们可以写出矩阵惩乘法的代码

struct JZ{  int m[maxn][maxn];   };
JZ muti(JZ a,JZ b)
{
    JZ temp;
    memset(temp.m,0,sizeof(temp.m));
    for(int i=0;i<maxn;i++)
        for(int j=0;j<maxn;j++){
            for(int k=0;k<maxn;k++)
            {
                temp.m[i][j]+=a.m[i][k]*b.m[k][j];
            }
            temp.m[i][j];
        }
    return temp;
}

对于方阵我们能够自己乘自己,就是乘幂运算。 我们参考快速幂,将数字的乘法换成矩阵的乘法,可以得出矩阵快速幂的代码;

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e8+5;
const int maxn=2; //定义方阵的阶数
struct JZ{  int m[maxn][maxn];   };//定义maxn阶方阵
JZ muti(JZ a,JZ b,int mod);
JZ quick_mod(JZ a,int k,int mod);
int main()
{
    JZ demo;
    JZ ans;
    int n;
    for(int i=0;i<maxn;i++)
    for(int j=0;j<maxn;j++) cin>>demo.m[i][j];
    while(cin>>n){
    ans=quick_mod(demo,n,MOD);
    for(int i=0;i<maxn;i++){
        for(int j=0;j<maxn;j++)
        cout<<ans.m[i][j]<<' ';
        cout<<endl;}
    }
}
JZ muti(JZ a,JZ b,int mod)
{
    JZ temp;
    memset(temp.m,0,sizeof(temp.m));
    for(int i=0;i<maxn;i++)
        for(int j=0;j<maxn;j++){
            for(int k=0;k<maxn;k++)
            {
                temp.m[i][j]+=(long long) a.m[i][k]*b.m[k][j]%mod;
            }
            temp.m[i][j]%=mod;
        }
    return temp;
}
JZ quick_mod(JZ a,int k,int mod)
{
    JZ ans;
    for(int i=0;i<maxn;i++)
        for(int j=0;j<maxn;j++)
            ans.m[i][j]=(i==j);
    while(k)  {
    if(k &1)  ans =muti(ans,a,mod);
    a = muti(a,a,mod);
    k >>=1;
    }
    return ans;
}

应用:矩阵快速幂求斐波那契数列。 我们定义一个矩阵A |0 1| |1 1| 定义F(0)=0,F(1)=1。 构成矩阵F矩阵|0 1| A矩阵的N次幂,乘以F矩阵的第一项就是第N个斐波那契数列。 证明: F矩阵乘以A矩阵代表将右侧元素给左侧,右侧元素等于右侧加左侧。矩阵的乘法满足结合律,所以FXX*……N……X = F (XXX……*X) 所以定义不同的F矩阵可以得到不同的斐波那契数列。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2019 Multi-University Training Contest 10 I Block Breaker

    Given a rectangle frame of size n×m. Initially, the frame is strewn with n×m squ...

    风骨散人Chiam
  • 数学--数论--HDU 2582 F(N) 暴力打表找规律

    This time I need you to calculate the f(n) . (3<=n<=1000000)

    风骨散人Chiam
  • Codeforce 140C (贪心+优先队列)补题

    C. New Year Snowmen time limit per test2 seconds memory limit per test256 mega...

    风骨散人Chiam
  • UESTC 485 Game(康托,BFS)

    Today I want to introduce an interesting game to you. Like eight puzzle, it is a...

    ShenduCC
  • UESTC 485 Game(康托展开,bfs打表)

    Game Time Limit: 4000/2000MS (Java/Others) Memory Limit: 65535/65535KB (Ja...

    ShenduCC
  • 快速排序(详解)

    描述: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序...

    张诺谦
  • 马走日(bfs)

    题目 江湖是什么,对于在象棋界厮杀的大钉来说, 江湖就是一个矩阵,他的目标,就是在江湖之中骑着马,从他的位置出发,走到终点。

    小二哥
  • 每日一题(8)

    解析: java在处理自增自减时,会使用临时变量存储,计算后再返回该值 自增自减原理一样,此处以自增为例

    KEN DO EVERTHING
  • C++ 传递动态内存

    这部分内容在引用作为函数的参数这个blog中有一些涉及,为了讨论引用传递顺带了参数传递与指针传递,在这里从动态内存传递的角度梳理一下,先看这样一个题目: 下...

    chaibubble
  • 奶牛异或

    链接:https://ac.nowcoder.com/acm/problem/22998?&headNav=acm 来源:牛客网

    glm233

扫码关注云+社区

领取腾讯云代金券