矩阵优化dp矩阵快速幂矩阵优化dp

112 阅读 0 评论 74 点赞

我是靠谱客的博主可耐背包，这篇文章主要介绍矩阵优化dp矩阵快速幂矩阵优化dp，现在分享给大家，希望可以做个参考。

文章目录

矩阵快速幂
- 矩阵乘法
- 快速幂
- P3390 【模板】矩阵快速幂
矩阵优化dp

矩阵快速幂

矩阵乘法

矩阵 $A, B$ 规模分别为 $n \times s, s \times m$ ，要进行矩阵乘法， $A, B$ 满足条件为"前列数=后行数"。 $C$ 为 $A, B$ 矩阵乘法结果，则C的规模变成 $n \times m$ , $C$ 第 $i$ 行第 $j$ 列的数字为A第i行每k个数乘B第j列每k个数： $C(i,j)=sum_{k=1}^{k=s}{A(i,k)×B(k,j)}$

快速幂

如果要算3的21次方，不做任何优化： $3 \times 3 = 9, 9 \times 3 = 27, 27 \times 3 = 81 . . .$ 一共做21次。
但是其实里面有很多重复计算的地方。让我们把21转化成2进制： $10101)_2$ 观察。
如下图：
在这里插入图片描述
将21的二进制最后一位称作第一位，第一位是1，那答案包含 $3^{(1)_2}$ ，接下来计算 $3^{(100)_2}$ ，我们发现 $100)_2$ 是 $1)_2$ 左移2位，体现在底数，就是底数自乘2次。只要让3不断自乘，同时幂数不断右移，当幂数最后一位是1时，就将当前的底数乘到答案上即可。以上算法的时间复杂度是O(log幂数)，因为n转化成二进制时的长度为log幂数。
设底数为a,幂数为b，一般答案会很大，一般会给你一个模数，在每次算出答案均取模。代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
LL ksm(LL a,LL b){
    LL ans=1;
    while(b){
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

P3390 【模板】矩阵快速幂

题目链接

复制代码

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>
#define LL long long
using namespace std;
const int N=110,mod=1e9+7;
int n;
struct Matrix{
    LL x[N][N];
    Matrix(){
        memset(x,0,sizeof x);
    }
};
Matrix operator*(const Matrix &a,const Matrix &b){
    Matrix tmp;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        	for(int k=0;k<n;k++)
            	tmp.x[i][j]=(tmp.x[i][j]+a.x[i][k]*b.x[k][j]%mod)%mod;
    return tmp;
}
Matrix Mksm(Matrix a,LL b){
    Matrix ans;
    for(int i=0;i<n;i++)
        ans.x[i][i]=1;
    while(b){
        if(b&1)
            ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
int main(){
    LL k;
    Matrix a;
    cin>>n>>k;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>a.x[i][j];
    Matrix b=Mksm(a,k);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<b.x[i][j]<<' ';
        }cout<<endl;
    }
    return 0;
}