矩阵模板

 1 //矩阵大小上限
 2 const int SIZ=100;
 3 int MOD=100;
 4 
 5 //矩阵大小为n*m，初始化全部为0
 6 struct mat
 7 {
 8     int n,m;
 9     int ar[SIZ][SIZ];
10     mat()
11     {
12         memset(ar,0,sizeof(ar));
13         n=m=SIZ;
14     };
15 };
16 
17 //矩阵乘法
18 mat operator *(mat a,mat b)
19 {
20     mat c;
21     c=mat();
22     c.n=a.n;
23     c.m=b.m;
24     for(int i=1;i<=a.n;i++)
25         for(int j=1;j<=b.n;j++)
26             if(a.ar[i][j]!=0)
27             for(int k=1;k<=a.m;k++)
28             {
29                 c.ar[i][k]+=(a.ar[i][j]*b.ar[j][k])%MOD;
30                 c.ar[i][k]%=MOD;
31             }
32     return c;
33 }
34 
35 //矩阵加法
36 mat operator +(mat a,mat b)
37 {
38     mat c;
39     c=mat();
40     c.n=a.n;
41     c.m=a.m;
42     for(int i=1;i<=a.n;i++)
43         for(int j=1;j<a.m;j++)
44             c.ar[i][j]=a.ar[i][j]+b.ar[i][j];
45     return c;
46 }
47 
48 //矩阵快速幂
49 mat operator ^(mat a,int k)
50 {
51     mat c;
52     c=mat();
53     c.n=a.n;
54     c.m=a.m;
55     for(int i=1;i<=a.n;i++)
56         c.ar[i][i]=1;
57     while(k)
58     {
59         if(k&1)
60             c=c*a;
61         a=a*a;
62         k/=2;
63     }
64     return c;
65 }
View Code