首页 > 代码库 > 洛谷 P3390 【模板】矩阵快速幂

洛谷 P3390 【模板】矩阵快速幂

这题的确是个模板

但也要提到有关矩乘的内容:

首先什么是矩阵

给一个线性变换

F(x)   (她可能就是个函数,定义域为向量集)

她可以把一个N维向量变成M维

那么显然x的每一维可能影响着F(x)的每一维,于是F(x)这个线性变换就应该是N*M个在每两维间的小映射构成的。

于是我们可以把她写成M行N列的矩阵(M行N列是出于习惯)

所以矩阵是用于形象的表示线性变换的工具

所以怎么合乎习惯的构造矩阵呢?

举例说明:

如,有一个三元组(3维向量)x{a,b,c}

定义F(x)={a+b,b+c}

那么可以构造矩阵(2*3的):

1 1 0

0 1 1

为什么是她呢?

其实矩阵的第i行表示x的每一维对F(x)的第i维的影响;

矩阵的i行j列,表示x的第j维以什么权值(其实是多少倍)影响F(x)第i维的构造;

x的所有维对F(x)的某一维的影响,即是F(x)这一维的结果;

如,对于上文中的矩阵;

把x{a,b,c}扔进去;

得到F(x)={1*a+1*b+0*c,0*a+1*b+1*c}={a+b,b+c}

然后什么是矩阵乘法呢?

线性变换作为一种映射,当然可以复合啦!

比如F(x)把五维向量变成四维,G(x)把四维向量变成三维;

那么G[F(x)]就能把五维向量变成三维了;

H(x)=G[F(x)];

那么H(x)的矩阵是什么呢?

她是G和F的乘积

如何相乘?

回到本题开头的例子:

F显然是个4*5的矩阵,G是3*4的

H应该是3*5(行数前列数后)

由上题给出的理解方式H[i,j](表示H的第i行第j列)

表示x的第j维对H(x)的第i行的影响

影响是怎么产生的呢?

Ej先是按照F第j列影响了F(x)的每一维

F(x)的每一维又按照G第i列影响了G[F(x)]的第i维

如下图的两矩阵(左边为G,右边F)

***   **
***   **
***   **
***

复合得

**
**
**
**

标记复合矩阵的某点

**
**
**
**

原矩阵的如下点贡献了复合矩阵的这个点

***   **
***   ** 
***   **
***

 所以H[i,j]=F[1,j]*G[i,1]+F[2,j]*G[i,2]+F[3,j]*G[i,3]+....啦

话说,你是可以得知H[i,j]与G,F中的那些值有关,但是你怎么得到具体的公式的呢?

这个公式的证明需要需要用到线性变换的性质——F(x+y)=F(x)+F(y)之类的(还是我之前已经用到了?),

由于篇幅,不好细证,其实举例就能理解的,

(就是这东西很好证,博主我不证啦)

 

然后是代码:

代码如下:

 1 #include<cstdio> 2 #include<cstring>  3 using namespace std; 4 struct ss{ 5     long long a[101][101]; 6 }; 7 ss re; 8 ss map; 9 ss ans;10 int n;11 long long m;12 ss mul(ss ,ss );13 int Sqr(long long );14 15 int main()16 {17     int i,j,k;18     scanf("%d%lld",&n,&m);19     for(i=1;i<=n;i++){20         for(j=1;j<=n;j++)21             scanf("%d",&map.a[i][j]);22         ans.a[i][i]=1;23     }24     Sqr(m);25     for(i=1;i<=n;i++){26         for(j=1;j<=n;j++)27             printf("%d ",ans.a[i][j]);28         printf("\n");29     }30     return 0;31 }32 33 int Sqr(long long m)34 {35     while(m){36         if(m&1)37             ans=mul(ans,map);38         m>>=1;39         map=mul(map,map);40     }41 }42 43 ss mul(ss x,ss y){44     int i,j,k;45     for(i=1;i<=n;i++)46         for(j=1;j<=n;j++){47             re.a[i][j]=0;48             for(k=1;k<=n;k++)49                 re.a[i][j]=(re.a[i][j]+x.a[i][k]*y.a[k][j])% 1000000007;50         }51     return re;52 }

祝AC哟;

 

洛谷 P3390 【模板】矩阵快速幂