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

矩阵快速幂

时间:2023-09-10 17:47:00浏览次数:44  
标签:Mat int 复杂度 矩阵 快速 dp 乘法

矩阵乘法的定义

矩阵 A* 矩阵 B = 矩阵 C

 

                                            

 

性质:满足结合律,分配率,但不满足交换律

矩阵乘法的特殊情形

矩阵 A 是一个 N*N 的矩阵,矩阵 F 是一个 N*1 的矩阵,设 F1= A*F,发现 F1也是一个 N*1 的矩阵,只有一行元素的矩阵,我们不妨把这些元素看成是一个个变量,而矩阵 F1 的变量通过矩阵 F 的变量的某种关系来实现更新,而这种关系通过矩阵 A 来实现(所以矩阵 A 也可以称作是系数矩阵?)

比如斐波那契数列,f[n+2]=f[n+1]+f[n],得出转移矩阵

 应用

上述的矩阵乘法的特殊情形常用于递推式,特别是当递推的次数达到一定的数量级,就可以用矩阵快速幂大大减少运算量,避免一些重复的计算。

矩阵快速幂

对于矩阵 F[n]=F[n-1]*A,可求出:

F[n=F[0]*pow(A,n)

A 的 n 次方需要一个 A 一个 A 来连乘获得吗?快速幂啊!

这样时间复杂度就降到了 log(n) 级,最终再乘上内部矩阵乘法所需的时间(三重循环)来得到最终的复杂度。

D. Magic Gems

n<=1e18,m<=200

我们要求空间为 n 的物品摆放方案数。

设 dp[i] 为空间为 i 的方案数,容易得出状态转移方程:

dp[i]=dp[i-1]+dp[i-m](i>=m)

令矩阵 F[n]={f[n],f[n-1],...,f[n-m+1]},F[n-1]={f[n-1],f[n-2],...,f[n-m]}

F[n]=F[n-1]*A

解得 A

 

 

由此可得,F[n]=F[m-1]*pow(A,n-m+1)

而矩阵乘法可以用快速幂优化,时间复杂度为 m*m*m*log(n)

暴力又优雅呢!

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
const int N=1e6+10;
int n,m,t,k,qq;
struct Mat{
    int a[110][110];
    Mat(){
        memset(a,0,sizeof(a));
    }
};
Mat operator*(Mat A,Mat B){
    Mat ret;
    for(int i=0;i<m;++i)
        for(int j=0;j<m;++j){
            int tmp=0;
            for(int k=0;k<m;++k)
                tmp=(tmp+A.a[i][k]*B.a[k][j])%mod;
            ret.a[i][j]=tmp;
        }
    return ret;
}
Mat power(Mat mat,int k){
    Mat ret;
    for(int i=0;i<m;++i)
        ret.a[i][i]=1;
    while(k){
        if(k&1) ret=ret*mat;
        mat=mat*mat;k>>=1;
    }
    return ret;
}
void solve(){
    cin>>n>>m;
    if(n<m) {cout<<1<<endl;return;}
    Mat mat;
    mat.a[0][0]=mat.a[0][m-1]=1;
    for(int i=1;i<m;++i) mat.a[i][i-1]=1;
    mat=power(mat,n-m+1);
    int ans=0;
    for(int i=0;i<m;++i) ans=(ans+mat.a[0][i])%mod;
    cout<<ans<<endl;
}
signed main(){
    int T=1;
    //cin>>T;
    while(T--) solve();
    return 0;
}
View Code

 

标签:Mat,int,复杂度,矩阵,快速,dp,乘法
From: https://www.cnblogs.com/buleeyes/p/17691550.html

相关文章

  • Excel单元格快速交换相邻位置内容
    一、相邻两列内容交换(A1与B1交换)1.首先选择A1单元格的边框位置,出现了向上下左右的十字标志2.此时按住shift键,并且拖向B1单元格的右边,出现"工"汉字标志3.松开鼠标,不松开shift键盘,完成A1与B1单元格的交换 二、相邻两行内容交换(A1与A2交换)1.首先选择A1单元格的边框位置,出现......
  • OpenResty快速入门
            ......
  • vue3探索——5分钟快速上手大菠萝pinia
    温馨提示:本文以vue3+vite+ts举例,vite配置和ts语法侧重较少,比较适合有vuex或者vue基础的小伙伴们儿查阅。安装piniayarnyarnaddpinianpmnpminstallpiniapnpmpnpmaddpinia1-开始方式一:在main.ts中直接引入pinia在src/main.ts中引入pinia(根存储),并传递给......
  • 使用【Python】快速生成本项目的requeirments.txt / pipreqs生成requirements.txt报
    使用【Python】快速生成本项目的requeirments.txt https://blog.csdn.net/qq_42076902/article/details/129417568pipreqs生成requirements.txt报错SyntaxError:invalidnon-printablecharacterU+FEFFhttps://blog.csdn.net/qq_51292462/article/details/128472993......
  • 如何快速体现自己的价值
    之前我们谈了如何证明自己的能力,当你感觉能力得到领导的认可之后,接下来你需要考虑的问题就是,如何快速体现自己的价值。证明能力很简单,但是体现价值就相对困难了。能够完成个人绩效,就能够证明你的个人能力;但是要想体现价值,那么需要为团队做出贡献。也就是说,如果你想体现出自己的价值......
  • 如何在试用期内,快速证明自己的能力
    每个公司在新人入职后一般都会有3个月时间的试用期,除非公司发现不适合这个岗位,或者通过试用期的表现认为不能胜任这个岗位,一般没有特殊情况,入职后都会顺利通过试用期,然后转正。1、为什么要快速证明自己的能力在这里我想说的是,转正不是新人入职的目的。作为一个新人入职公司以后,应......
  • 作为新人,如何快速了解公司的业务
    开发人员想要在公司发展得好,开发质量高,进度快,除了自身技术水平过硬以外,一个重要的因素就是要了解公司的业务,了解业务需求,只有对业务和需求有深刻的理解,才能开发出符合产品要求的软件。那么进入新公司以后,想要快速了解公司的业务,可以按照以下三个原则来进行,如下图:1、搜索进入公司后,......
  • Lucy v1.7.9 快速启动软件
    概述lucy是一个开发者觉得Lily用的不太顺手,所以就又重新开发了一个。用过音速启动、Lily等启动工具,都是很好的软件。但每个软件都不可能适应所有人的需求,于是自己又造了一个轮子。使用Lily时习惯吧名字改为Lucy,于是轮子的名字依然叫Lucy了。软件最大特色就是简洁,只为快速启动,简洁......
  • 新人如何快速学会Python
    要快速学会Python,首先要了解Python的基本语法和数据类型。Python是一种解释型语言,具有简单易学、高效开发、库丰富等特点。首先,需要掌握Python的基本语法,例如变量、数据类型、控制流语句、函数等。可以通过阅读官方文档、在线教程、书籍等方式进行学习。同时,可以尝试编写简单的Pyt......
  • 教你快速上手C语言中的数据类型和变量
    (章节目录)前言  哈喽,各位铁汁们好啊!✨今天来给大家带来的是初识C语言里面的数据类型和变量。  今天主要带大家简单认识-一下C语言,俗话说没吃过猪肉,也见过猪跑。了解下每个数据类型是干嘛的。可以读懂C语言的简单程序,其他的博主就不多介绍了。  后面会为大家详细介绍......