前面几篇随笔中介绍了利用矩阵乘法(特别是应用快速幂运算)解决递推快速求值、置换和几何变换等问题的方法。实际上矩阵乘法的应用远不止这些,下面通过几个实例来介绍下矩阵乘法的其它一些典型的应用。
【例1】多少条道。
给定一个有向图,问从a点恰好走k步(允许重复经过边)到达b点的方案数mod p的值。
(1)编程思路。
本题是矩阵乘法应用在图论中的一个典型方法。
给定了有向图,可以得到该图的邻接矩阵a,在邻接矩阵a中,a(i,j)=1当且仅当存在一条边i->j。若i->j不存在直接相连接的边,则a(i,j)=0。
令c=a*a,那么 c(i,j)= σa(i,k)*a(k,j),实际上就等于从点i到点j恰好经过2条边的路径数(k为中转点)。
类似地,c*a =a*a*a的第i行第j列就表示从i到j经过3条边的路径数。同理,如果要求经过k步的路径数,只需要采用快速幂运算求出a^k即可。
(2)源程序。
#include <stdio.h>
#include <string.h>
#define mod 1000
struct matrix
{
int mat[21][21]; // 存储矩阵中各元素
};
matrix matmul(matrix a ,matrix b,int n,int m)
{
matrix c;
memset(c.mat,0,sizeof(c.mat));
int i,j,k;
for (k = 1; k<=n ; k++)
for (i=1 ;i<=n ; i++)
if (a.mat[i][k]!=0)
for (j = 1 ;j<=n ;j++)
c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % m;
return c;
}
matrix quickmatpow(matrix a ,int n,int b,int m) // n阶矩阵a快速b次幂
{
matrix c;
memset(c.mat ,0 ,sizeof(c.mat));
int i;
for (i = 1 ;i <= n ;i++)
c.mat[i][i] = 1;
while (b!=0)
{
if (b & 1)
c = matmul(c ,a ,n,m); // c=c*a;
a = matmul(a ,a ,n,m); // a=a*a
b /= 2;
}
return c;
}
int main()
{
int n,m,s,t,ncase,a,b,k,i;
matrix p,ans;
while (scanf(“%d%d”,&n,&m) && n+m!=0)
{
memset(p.mat,0,sizeof(p.mat));
for (i=1;i<=m;i++)
{
scanf(“%d%d”,&s,&t);
p.mat[s+1][t+1]=1;
}
scanf(“%d”,&ncase);
for (i=1;i<=ncase;i++)
{
scanf(“%d%d%d”,&a,&b,&k);
ans=quickmatpow(p,n,k,mod);
printf(“%dn” ,ans.mat[a+1][b+1]);
}
}
return 0;
}
将此源程序提交给 hdu 2157 “how many ways??”,可以accepted。
我们知道,构造好平移、缩放或旋转的转换矩阵后,可以实现几何变换;构造好置换矩阵后,可以实现置换操作。这样,在一些问题中,我们也可以根据状态变化的情况,构造一个状态转移矩阵,来解决一些状态变换类问题。
【例2】灯的状态。
有n盏灯排成一排,开关状态已知,0代表灯熄灭,1代表点亮。每过一秒:第i(1<=i<=n)盏灯会根据刚才左边的那个灯的开关情况变化,如果左边的灯是亮的,它就会变化,如果左边的灯是熄灭的,它就保持原来状态。第1盏灯的左边是最后一盏灯。问m秒后全部n盏灯的状态。
(1)编程思路。
构造好状态转移矩阵p,p^m的结果就是m秒后的状态转移矩阵。再将状态转移矩阵除以n盏灯初始状态列向量s即可得到n盏灯的最终状态。
(2)源程序。
#include <stdio.h>
#include <string.h>
#define mod 2
struct matrix
{
int mat[101][101]; // 存储矩阵中各元素
};
matrix matmul(matrix a ,matrix b,int n)
{
matrix c;
memset(c.mat,0,sizeof(c.mat));
int i,j,k;
for (k = 1; k<=n ; k++)
for (i=1 ;i<=n ; i++)
if (a.mat[i][k]!=0)
for (j = 1 ;j<=n ;j++)
c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % mod;
return c;
}
matrix quickmatpow(matrix a ,int n,int b) // n阶矩阵a快速b次幂
{
matrix c;
memset(c.mat ,0 ,sizeof(c.mat));
int i;
for (i = 1 ;i <= n ;i++)
c.mat[i][i] = 1;
while (b!=0)
{
if (b & 1)
c = matmul(c ,a ,n); // c=c*a;
a = matmul(a ,a ,n); // a=a*a
b /= 2;
}
return c;
}
int main()
{
int m,n,i,j,s;
char f[101];
int temp[101],ans[101];
matrix p;
while(scanf(“%d” ,&m)!=eof)
{
scanf(“%s”,f);
n=strlen(f);
for (i=1;i<=n;i++)
temp[i]=f[i-1]-‘0’;
memset(p.mat,0,sizeof(p.mat));
p.mat[1][1]=p.mat[1][n]=1;
for (i=2;i<=n;i++)
p.mat[i][i-1]=p.mat[i][i]=1;
p = quickmatpow(p,n,m);
for (i=1;i<=n;i++)
{
s=0;
for (j=1;j<=n;j++)
s+=p.mat[i][j]*temp[j];
ans[i]=s%mod;
}
for (i=1;i<=n;i++)
printf(“%d” ,ans[i]);
printf(“n”);
}
return 0;
}
将此源程序提交给 hdu 2276 “kiki & little kiki 2”,可以accepted。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/601999.html