前面几篇随笔中介绍了利用矩阵乘法（特别是应用快速幂运算）解决递推快速求值、置换和几何变换等问题的方法。实际上矩阵乘法的应用远不止这些，下面通过几个实例来介绍下矩阵乘法的其它一些典型的应用。

【例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("%d\n" ,ans.mat[a+1][b+1]);
             }
      }
      return 0;
}

将此源程序提交给 HDU 2157 “How many ways??”，可以Accepted。

 

       我们知道，构造好平移、缩放或旋转的转换矩阵后，可以实现几何变换；构造好置换矩阵后，可以实现置换操作。这样，在一些问题中，我们也可以根据状态变化的情况，构造一个状态转移矩阵，来解决一些状态变换