矩阵快速幂 POJ3735

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 
  5 using namespace std;
  6 
  7 //矩阵大小上限
  8 const int SIZ=110;
  9 int MOD=1000000000;
 10 
 11 //矩阵大小为n*m，初始化全部为0
 12 struct mat
 13 {
 14     int n,m;
 15     long long ar[SIZ][SIZ];
 16     mat()
 17     {
 18         memset(ar,0,sizeof(ar));
 19         n=m=SIZ;
 20     };
 21 };
 22 
 23 //矩阵乘法
 24 mat operator *(mat a,mat b)
 25 {
 26     mat c;
 27     c=mat();
 28     c.n=a.n;
 29     c.m=b.m;
 30     for(int i=1;i<=a.n;i++)
 31         for(int j=1;j<=b.n;j++)
 32         {
 33             if(a.ar[i][j]!=0)
 34                 for(int k=1;k<=b.m;k++)
 35                 {
 36                     c.ar[i][k]+=(a.ar[i][j]*b.ar[j][k]);
 37                 }
 38         }
 39     return c;
 40 }
 41 
 42 //矩阵加法
 43 mat operator +(mat a,mat b)
 44 {
 45     mat c;
 46     c=mat();
 47     c.n=a.n;
 48     c.m=a.m;
 49     for(int i=1;i<=a.n;i++)
 50         for(int j=1;j<a.m;j++)
 51             c.ar[i][j]=a.ar[i][j]+b.ar[i][j];
 52     return c;
 53 }
 54 
 55 //矩阵快速幂
 56 mat operator ^(mat a,int k)
 57 {
 58     mat c;
 59     c=mat();
 60     c.n=a.n;
 61     c.m=a.m;
 62     for(int i=1;i<=a.n;i++)
 63         c.ar[i][i]=1;
 64     while(k)
 65     {
 66         if(k&1)
 67             c=c*a;
 68         a=a*a;
 69         k/=2;
 70     }
 71     return c;
 72 }
 73 
 74 int main()
 75 {
 76     int n,m,k;
 77     while(scanf("%d%d%d",&n,&m,&k)&&(n||k||m))
 78     {
 79         char a[12];
 80         mat mat1;
 81         mat1.n=mat1.m=n+1;
 82         for(int i=1;i<=mat1.m;i++)
 83             mat1.ar[i][i]=1;
 84         for(int i=0;i<k;i++)
 85         {
 86             int b=0;
 87             int c=0;
 88             scanf("%s",a);
 89             if(a[0]=='g')
 90             {
 91                 scanf("%d",&b);
 92                 mat1.ar[b][mat1.m]+=1;
 93             }
 94             if(a[0]=='e')
 95             {
 96                 scanf("%d",&b);
 97                 for(int i=1;i<=mat1.m;i++)
 98                 {
 99                     mat1.ar[b][i]=0;
100                 }
101             }
102             if(a[0]=='s')
103             {
104                 scanf("%d%d",&b,&c);
105                 for(int i=1;i<=mat1.m;i++)
106                 {
107                     swap(mat1.ar[b][i],mat1.ar[c][i]);
108                 }
109             }
110         }
111         mat mat3=mat1^m;
112         mat mat4;
113         mat4.n=n+1;
114         mat4.m=1;
115         mat4.ar[mat4.n][1]=1;
116         mat ans=mat3*mat4;
117         printf("%lld",ans.ar[1][1]);
118         for(int i=2;i<=n;i++)
119             printf(" %lld",ans.ar[i][1]);
120         printf("
");
121     }
122     return 0;
123 }
View Code
优化的矩阵乘法