【OI之路】02数论算法-4矩阵乘法

2.4.1定义

矩阵乘法:用来求某种递推关系。
矩阵相乘只有在第一个矩阵的列数和第二个矩阵的行数相同时才有意义。
设A为A*M的矩阵,B为M*B的矩阵,那么矩阵C为矩阵A与B的乘积,
其中矩阵C中的第i行第j列元素可以表示为:


如下所示:

2.4.2例题

【题目描述】
a[1]=a[2]=a[3]=1
a[x]=a[x-3]+a[x-1] (x>3)
求a数列的第n项对1000000007(10^9+7)取余的值。
【输入格式】
第一行一个整数T,表示询问个数。
以下T行,每行一个正整数n。
【输出格式】
每行输出一个非负整数表示答案。
【样例输入】
3
6 8 10
【样例输出】
4 9 19
【数据范围】
T<=100,n<=2*10^9

开一个2*2的矩阵:主要是为了快速幂的方便,一个可以和自己乘上许多次(>=2)的矩阵只有可能是正方形的,所以要开这样一个矩阵。
然后就是使用矩阵乘法来递推。
如果想要预处理,也是可以的,只不过T<=100,所以偷懒省空间。

2.4.3代码

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
struct mod
{
long long a[4][4];
mod() { memset(a,0,sizeof(a)); }
};
mod mul(mod a,mod b)//矩阵乘法
{
mod c;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
for(int k=1;k<=3;k++)
c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%1000000007;
return c;
}
void make(int n)
{
mod a,c;
c.a[1][1]=1;c.a[2][1]=1;c.a[3][1]=1;
a.a[1][1]=0;a.a[1][2]=1;a.a[1][3]=0;
a.a[2][1]=0;a.a[2][2]=0;a.a[2][3]=1;
a.a[3][1]=1;a.a[3][2]=0;a.a[3][3]=1;
n++;
while(n>0)//快速幂
{
if(n&1) c=mul(c,a);//不能是mul(a,c)
a=mul(a,a);//(A^n)*B
n>>=1;
}
printf("%d\n",c.a[3][3]%1000000007);
}
int main(int argc,char *argv[])
{
int t;scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
make(n);
}
}

2.4.4正文开始!

咳咳,上面的部分是我以前对于所谓矩阵乘法的浅显认知。
首先,矩阵乘法经典中的经典:Matrix67
矩阵乘法的精髓在于:能通过快速幂将操作简化

顺便介绍几个特殊01矩阵:
单位矩阵,m[i][i]=1,其他是0,所有矩阵和它乘都是自己,相当于1
邻接矩阵,m[i][j]=1表示从i能到j

再顺便说一下,通常而言,表示一个状态应该使用列向量,
也就是一个a行1列的矩阵

2.4.5 众多练习题

重点与精华,顺序不重要
好吧虽然我写的时候是按照我的思路来写的
所以如果有空的话,顺着做当然最好啦~
题目好像真的蛮多的
Tag-矩阵乘法

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/c6a2.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%