矩阵快速幂
首先知道矩阵
矩阵(Matrix)是一个按照长方阵列排列的复数或实数集合;
矩阵乘法:
定义:设
A为
m×p
的矩阵,
B为
p×n
的矩阵,那么称
m×n
的矩阵
C为矩阵
A与
B的乘积,记作
C=A×B
,其中矩阵C中的第
i
行第
j
列元素可以表示为:


知道矩阵乘法之后,比如菲波那切数列就是一个递推式,
F(n)=F(n-1)+F(n-2); 因为矩阵乘法,所以
设 矩阵 A为

矩阵 B 为

则 A*B 则为 F(n)= F(n-1)*1+F(n-2)*1
因为我们需要的矩阵为 A*B 的矩阵为

所以倒推到 B 矩阵 ,则 B矩阵是
,

所以 F(n) 的矩阵为 初始矩阵 * (B^(n-2)) n>=3;
所得到的矩阵 A[0][0] 就是F(n) 的值,时间复杂度优化的地方就是在幂指数的那部分快速幂,节约了时间。
所以关键就在于 从 递推式构造矩阵
比如:

这个构造出来的矩阵就是

自己可以写出这个矩阵,就明白了;下面给一个简单的题目,练练手。
给一个简单的练习题: 点击打开链接
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
typedef long long LL;
const int INF=2e9+1e8;
const int MOD=1000007;
const int MAX_SIZE=1005;
const int MM=3;
LL f1,f2,a,b,c,n;
struct Mat
{
LL maze[MM][MM];
void set_empty()
{
memset(maze,0,sizeof(maze));
}
};
Mat unit_Mat=
{
1,0,0,
0,1,0,
0,0,1
}; // 定义一个单位矩阵,任何一个矩阵 乘以 单位矩阵,其值等于本身;
Mat operator *(Mat a,Mat b) // 重载运算符 * // 定义两个矩阵的乘法,根据矩阵乘法的定义来写
{
Mat c;
c.set_empty(); // 一定要设置为空。清零数组;不然后面加等一个数会有垃圾值
LL i,j,k;
for(i=0; i<MM; i++)
{
for(j=0; j<MM; j++)
{
for(k=0; k<MM; k++)
{
c.maze[i][j]+=a.maze[i][k] * b.maze[k][j];
c.maze[i][j] %= MOD;
}
}
}
return c;
}
Mat operator^(Mat a,LL N) // 优化时间的就在此处,
// 类似与一般的int 数字的快速幂求值,思想是一样的。不懂可百度快速幂。
{
Mat c=unit_Mat;
while(N)
{
if(N&1) c=a*c;
a=a*a;
N>>=1;
}
return c;
}
void solve()
{
Mat A,B;
B.set_empty();
A.set_empty();
B.maze[0][0]=b,B.maze[1][0]=a,B.maze[2][0]=c;
B.maze[0][1]=B.maze[2][2]=1;
B=B^(n-2);
A.maze[0][0]=f2,A.maze[0][1]=f1,A.maze[0][2]=1;
LL ans=0;
Mat C=A*B;
printf("%lldn",(C.maze[0][0]+MOD)%MOD);
}
int main()
{
int times;
scanf("%d",×);
while(times--)
{
scanf("%lld %lld %lld %lld %lld %lld",&f1,&f2,&a,&b,&c,&n);
if(n == 1)
printf("%lldn",(f1+MOD)%MOD);
else if(n == 2)
printf("%lldn",(f2+MOD)%MOD);
else solve(); // 其上位特判 因为公式的定义域是 n>=3;
}
return 0;
}
最后
以上就是现实心情最近收集整理的关于矩阵快速幂 ——(递推表达式)的全部内容,更多相关矩阵快速幂内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复