【例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;
}