矩阵小结

看了世界冠军的博客，发现矩阵真是个强大的东西，好多东西都可以通过找规律来用矩阵运算解决。。

首先推荐两个博客，供读者学习矩阵运算。。

http://www.matrix67.com/blog/archives/276 matrix67的博客，这个不得不提。。orz

http://www.cnblogs.com/frog112111/category/480666.html这个博客里有矩阵十题的出处和讲解了部分如何很好的构造矩阵

下面列出我做的几道矩阵的题目:

http://acm.hdu.edu.cn/showproblem.php?pid=1575 hdu 1575 Tr A

很经典的矩阵，fib数列可以通过矩阵来实现之间的运算

题目要求A^k，红果果的快速幂矩阵乘法

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <queue>
 6 using namespace std;
 7 const int N = 15;
 8 const int MOD = 9973;
 9 struct Matrix
10 {
11     int mat[N][N];
12 }p;
13 int n;
14 Matrix mult(Matrix a,Matrix b)
15 {
16     int i,j,k;
17     Matrix ans;
18     for(i=0;i<n;i++)
19         for(j=0;j<n;j++)
20         {
21             ans.mat[i][j]=0;
22             for(k=0;k<n;k++)
23                 ans.mat[i][j]=(ans.mat[i][j]+a.mat[i][k]*b.mat[k][j])%MOD;
24         }
25     return ans;
26 }
27 Matrix powmod(int m)
28 {
29     Matrix ans;
30     int i,j;
31     for(i=0;i<n;i++)
32         for(j=0;j<n;j++)
33             ans.mat[i][j]=(i==j);
34     while(m)
35     {
36         if(m&1)
37             ans=mult(ans,p);
38         p=mult(p,p);
39         m>>=1;
40     }
41     return ans;
42 }
43 int main()
44 {
45     int t,k,i,j;
46     Matrix ans;
47     scanf("%d",&t);
48     while(t--)
49     {
50         scanf("%d%d",&n,&k);
51         for(i=0;i<n;i++)
52             for(j=0;j<n;j++)
53                 scanf("%d",&p.mat[i][j]);
54         ans=powmod(k);
55         int sum=0;
56         for(i=0;i<n;i++)
57             sum=(sum+ans.mat[i][i])%MOD;
58         printf("%d
",sum);
59     }
60     return 0;
61 }

View Code

http://acm.hdu.edu.cn/showproblem.php?pid=1757 hdu 1757 a simple math problem

构造方法可以看上面的第二个博客中的思路，这个也可以递推出来。

a0 1 0 0 0 0 0 0 0 0

a1 0 1 0 0 0 0 0 0 0

a2 0 0 1 0 0 0 0 0 0

a3 0 0 0 1 0 0 0 0 0

a4 0 0 0 0 1 0 0 0 0

a5 0 0 0 0 0 1 0 0 0

a6 0 0 0 0 0 0 1 0 0

a7 0 0 0 0 0 0 0 1 0

a8 0 0 0 0 0 0 0 0 1

a9 0 0 0 0 0 0 0 0 0

然后同第一题的方法就行了

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <queue>
 6 using namespace std;
 7 const int N = 15;
 8 #define ll long long
 9 struct matrix
10 {
11     ll mat[10][10];
12 }f;
13 int k,mod;
14 matrix mult(matrix a,matrix b)
15 {
16     int i,j,k;
17     matrix ans;
18     for(i=0;i<10;i++)
19         for(j=0;j<10;j++)
20         {
21             ans.mat[i][j]=0;
22             for(k=0;k<10;k++)
23                 ans.mat[i][j]=(ans.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod;
24         }
25     return ans;
26 }
27 matrix powmod(matrix a,int m)
28 {
29     matrix ans;
30     for(int i=0;i<10;i++)
31         for(int j=0;j<10;j++)
32             ans.mat[i][j]=(i==j);
33     while(m)
34     {
35         if(m&1)
36             ans=mult(ans,a);
37         a=mult(a,a);
38         m>>=1;
39     }
40     return ans;
41 }
42 int main()
43 {
44     int a[10];
45     while(scanf("%d%d",&k,&mod)!=EOF)
46     {
47         if(k<10)
48         {
49             printf("%d
",k%mod);
50             continue;
51         }
52         int i;
53         memset(f.mat,0,sizeof(f.mat));
54         for(i=0;i<10;i++)
55             scanf("%d",&a[i]);
56         for(i=0;i<10;i++)
57         {
58             f.mat[i][0]=a[i];
59             if(i+1<10)
60             f.mat[i][i+1]=1;
61         }
62         matrix ans;
63         ans=powmod(f,k-9);
64         ll sum=0;
65         for(i=0;i<10;i++)
66             sum=(sum+(9-i)*ans.mat[i][0])%mod;
67         printf("%lld
",sum);
68     }
69     return 0;
70 }

View Code

http://acm.hdu.edu.cn/showproblem.php?pid=1588 hdu 1588 Gauss Fibonacci

同样这个还是fib的矩阵。但题中要求的是the sum of every f(g(i)) for 0<=i<n

即f(b)+f(k+b)+...==>A^b+A^(k+b)+...==>A^b(E+A^K+A^2k+....)

另B=A^k==>A^b(E+B+B^2+...) A^b和B都可以用快速幂算出。。后面的部分，matrix67博客有提到用二分法求出

也可以利用poj sumdiv的二分思想写这个。。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <queue>
 6 using namespace std;
 7 const int N = 15;
 8 #define ll long long
 9 int k,b,n,M;
10 struct matrix
11 {
12     ll mat[2][2];
13 } fib,one;
14 matrix mult(matrix a,matrix b)
15 {
16     matrix ans;
17     int i,j,k;
18     for(i=0; i<2; i++)
19         for(j=0; j<2; j++)
20         {
21             ans.mat[i][j]=0;
22             for(k=0; k<2; k++)
23                 ans.mat[i][j]=(ans.mat[i][j]+a.mat[i][k]*b.mat[k][j])%M;
24         }
25     return ans;
26 }
27 matrix add(matrix a,matrix b)
28 {
29     matrix ans;
30     int i,j;
31     for(i=0; i<2; i++)
32         for(j=0; j<2; j++)
33             ans.mat[i][j]=(a.mat[i][j]+b.mat[i][j])%M;
34     return ans;
35 }
36 matrix powmod(matrix a,int m)
37 {
38     matrix ans;
39     int i,j;
40     for(i=0; i<2; i++)
41         for(j=0; j<2; j++)
42             ans.mat[i][j]=(i==j);
43     while(m)
44     {
45         if(m&1)
46             ans=mult(ans,a);
47         a=mult(a,a);
48         m>>=1;
49     }
50     return ans;
51 }
52 matrix summod(matrix a,int m)
53 {
54     /*if(m==0)
55         return one;
56     if(m&1) return  mult(summod(a,m/2),add(one,powmod(a,m/2+1)));
57     else    return add(powmod(a,m/2),mult(summod(a,m/2-1),add(one,powmod(a,m/2+1))));
58     */
59     if(m==1)
60         return a;
61     matrix t=summod(a,m>>1);
62     t=add(t,mult(t,powmod(a,m>>1)));
63     if(m&1)
64         return add(t,powmod(a,m));
65     else
66         return t;
67 
68 }
69 int main()
70 {
71 
72     while(scanf("%d%d%d%d",&k,&b,&n,&M)!=EOF)
73     {
74         matrix ans,sum;
75         fib.mat[0][0]=fib.mat[0][1]=fib.mat[1][0]=1;
76         fib.mat[1][1]=0;
77         one.mat[0][0]=one.mat[1][1]=1;
78         one.mat[0][1]=one.mat[1][0]=0;
79         ans=powmod(fib,b);
80         sum=powmod(fib,k);
81         sum=add(one,summod(sum,n-1));
82         //sum=summod(sum,n-1);
83         sum=mult(sum,ans);
84         printf("%lld
",sum.mat[0][1]);
85     }
86     return 0;
87 }

View Code

http://acm.hdu.edu.cn/showproblem.php?pid=2157 hdu 2157 how many ways??

这是矩阵解法的用一个经典的使用。。有向图的可达矩阵的K次幂，就是走k步的方法数//（早知道离散好好学的T^T）

所以构造出可达矩阵之后，快速幂运算即可。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <queue>
 6 using namespace std;
 7 const int N = 25;
 8 const int mod =1000;
 9 #define ll long long
10 struct matrix
11 {
12     int mat[N][N];
13 }f;
14 int n,m;
15 matrix mult(matrix a,matrix b)
16 {
17     int i,j,k;
18     matrix ans;
19     for(i=0;i<n;i++)
20         for(j=0;j<n;j++)
21         {
22             ans.mat[i][j]=0;
23             for(k=0;k<n;k++)
24                 ans.mat[i][j]=(ans.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod;
25         }
26     return ans;
27 }
28 matrix powmod(matrix a,int m)
29 {
30     matrix ans;
31     for(int i=0;i<n;i++)
32         for(int j=0;j<n;j++)
33             ans.mat[i][j]=(i==j);
34     while(m)
35     {
36         if(m&1)
37             ans=mult(ans,a);
38         a=mult(a,a);
39         m>>=1;
40     }
41     return ans;
42 }
43 int main()
44 {
45     int u,v,t,a,b,k;
46     while(scanf("%d%d",&n,&m)&&(n+m))
47     {
48         memset(f.mat,0,sizeof(f.mat));
49         while(m--)
50         {
51             scanf("%d%d",&u,&v);
52             f.mat[u][v]=1;
53         }
54         scanf("%d",&t);
55         while(t--)
56         {
57             scanf("%d%d%d",&a,&b,&k);
58             matrix ans=powmod(f,k);
59             printf("%d
",ans.mat[a][b]);
60         }
61     }
62     return 0;
63 }

View Code

http://acm.hdu.edu.cn/showproblem.php?pid=2256 hdu 2256 problem of precision

这题的神构造=。=

然后初始化的状态是(5,2);另外因为要求的是最接近的整数。可以利用其共轭式

1''(5+2*sqrt(6)）^n = xn+ yn*sqrt(6) 2''(5 - 2*sqrt(6)）^n=xn-yn*sqrt(6)

(5+2*sqrt(6)）^n + （5-2*sqrt(6)）^n = 2 * xn 而(5-2*sqrt(6))^n 会无限趋近于0

所以（5+2*sqrt(6)）^n= 2*xn-（5 - 2*sqrt(6)）^n 然后在向下取整得到的便是 2*xn-1

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <queue>
 6 using namespace std;
 7 const int N = 2;
 8 const int mod =1024;
 9 #define ll long long
10 struct matrix
11 {
12     ll mat[N][N];
13 }f,E,b;
14 matrix mult(matrix a,matrix b,int n)
15 {
16     int i,j,k;
17     matrix ans;
18     for(i=0;i<n;i++)
19         for(j=0;j<n;j++)
20         {
21             ans.mat[i][j]=0;
22             for(k=0;k<n;k++)
23                 ans.mat[i][j]=(ans.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod;
24         }
25     return ans;
26 }
27 matrix add(matrix a ,matrix b,int n)
28 {
29     int i,j;
30     matrix ans;
31     for(i=0;i<n;i++)
32         for(j=0;j<n;j++)
33             ans.mat[i][j]=(a.mat[i][j]+b.mat[i][j])%mod;
34     return ans;
35 }
36 matrix powmod(matrix a,int m,int n)
37 {
38     matrix ans;
39     for(int i=0;i<n;i++)
40         for(int j=0;j<n;j++)
41             ans.mat[i][j]=(i==j);
42     while(m)
43     {
44         if(m&1)
45             ans=mult(ans,a,n);
46         a=mult(a,a,n);
47         m>>=1;
48     }
49     return ans;
50 }
51 matrix summod(matrix a,int k,int n)
52 {
53     if(k==1)    return a;
54     if(k&1) return add(powmod(a,k,n),summod(a,k-1,n),n);
55     else    return mult(add(E,powmod(a,k>>1,n),n),summod(a,k>>1,n),n);
56 }
57 int main()
58 {
59     int t;
60     scanf("%d",&t);
61     while(t--)
62     {
63         int n;
64         scanf("%d",&n);
65         f.mat[0][0]=5,f.mat[0][1]=12;
66         f.mat[1][0]=2,f.mat[1][1]=5;
67         b.mat[0][0]=5,b.mat[0][1]=0;
68         b.mat[1][0]=2,b.mat[1][1]=0;
69         matrix ans=powmod(f,n-1,2);
70         ans=mult(ans,b,2);
71         printf("%d
",(2*ans.mat[0][0]-1+mod)%mod);
72     }
73     return 0;
74 }

View Code

http://acm.hdu.edu.cn/showproblem.php?pid=2254 hdu 2254 奥运

思路跟2157差不多，注意一些细节问题就好了。。

要求的是A^t1+A^(t1+1)+...+A^t2=A^(t1-1)(A+A^2+...+A^(t2-t1+1))

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <queue>
  6 #include <map>
  7 #include <string>
  8 using namespace std;
  9 const int N = 35;
 10 const int mod =2008;
 11 #define ll long long
 12 struct matrix
 13 {
 14     int mat[N][N];
 15 } f,E,b;
 16 matrix mult(matrix a,matrix b,int n)
 17 {
 18     int i,j,k;
 19     matrix ans;
 20     for(i=0; i<n; i++)
 21         for(j=0; j<n; j++)
 22         {
 23             ans.mat[i][j]=0;
 24             for(k=0; k<n; k++)
 25                 ans.mat[i][j]=(ans.mat[i][j]+(a.mat[i][k]%mod*b.mat[k][j]%mod)%mod)%mod;
 26         }
 27     return ans;
 28 }
 29 matrix add(matrix a ,matrix b,int n)
 30 {
 31     int i,j;
 32     matrix ans;
 33     for(i=0; i<n; i++)
 34         for(j=0; j<n; j++)
 35             ans.mat[i][j]=(a.mat[i][j]+b.mat[i][j])%mod;
 36     return ans;
 37 }
 38 matrix powmod(matrix a,int m,int n)
 39 {
 40     matrix ans;
 41     for(int i=0; i<n; i++)
 42         for(int j=0; j<n; j++)
 43             ans.mat[i][j]=(i==j);
 44     while(m)
 45     {
 46         if(m&1)
 47             ans=mult(ans,a,n);
 48         a=mult(a,a,n);
 49         m>>=1;
 50     }
 51     return ans;
 52 }
 53 matrix summod(matrix a,int k,int n)
 54 {
 55     if(k==1)    return a;
 56     if(k&1) return add(powmod(a,k,n),summod(a,k-1,n),n);
 57     else    return mult(add(E,powmod(a,k>>1,n),n),summod(a,k>>1,n),n);
 58 }
 59 int main()
 60 {
 61     int n,i,j;
 62     char u[100],v[100];
 63     map<string,int>mp;
 64     while(scanf("%d",&n)!=EOF)
 65     {
 66         mp.clear();
 67         int cnt=0;
 68         memset(f.mat,0,sizeof(f.mat));
 69         while(n--)
 70         {
 71             scanf("%s%s",u,v);
 72             if(mp.find(u)==mp.end())
 73                 mp[u]=cnt++;
 74             if(mp.find(v)==mp.end())
 75                 mp[v]=cnt++;
 76             f.mat[mp[u]][mp[v]]++;
 77         }
 78         int k,t1,t2;
 79         char v1[100],v2[100];
 80         scanf("%d",&k);
 81         for(i=0; i<cnt; i++)
 82             for(j=0; j<cnt; j++)
 83                 E.mat[i][j]=(i==j);
 84         while(k--)
 85         {
 86             scanf("%s%s%d%d",v1,v2,&t1,&t2);
 87             if(mp.find(v1)==mp.end())
 88             {
 89                 printf("0
");
 90                 continue;
 91             }
 92             if(mp.find(v2)==mp.end())
 93             {
 94                 printf("0
");
 95                 continue;
 96             }
 97             if(t1==0&&t2==0)
 98             {
 99                 printf("0
");
100                 continue;
101             }
102             if(t1>t2)
103                 t1^=t2^=t1^=t2;
104             if(t1<=1)
105             {
106                 matrix ans=summod(f,t2,cnt);
107                 printf("%d
",(ans.mat[mp[v1]][mp[v2]]+mod)%mod);
108             }
109             else
110             {
111                 matrix ans=summod(f,t2-t1+1,cnt);
112                 matrix tmp=powmod(f,t1-1,cnt);
113                 ans=mult(tmp,ans,cnt);
114                 printf("%d
",(ans.mat[mp[v1]][mp[v2]]+mod)%mod);
115             }
116         }
117     }
118     return 0;
119 }

View Code

http://acm.hdu.edu.cn/showproblem.php?pid=2276 hdu 2276 Kiki & Little Kiki 2

因为每个的关系都跟它前一个和它本身有关，可以构造矩阵:

1 1 0 0 0 0 0

0 1 1 0 0 0 0

0 0 1 1 0 0 0

0 0 0 1 1 0 0

0 0 0 0 1 1 0

0 0 0 0 0 1 1

1 0 0 0 0 0 1

然后就可以解决了。交了几次都是tle=.=看网上说用位运算可以加快速度。。。好强大的位运算。。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <queue>
 6 #include <map>
 7 #include <string>
 8 using namespace std;
 9 const int N = 110;
10 const int mod =2;
11 #define ll long long
12 struct matrix
13 {
14     int mat[N][N];
15 } f,E,B;
16 matrix mult(matrix a,matrix b,int n)
17 {
18     int i,j,k;
19     matrix ans;
20     for(i=0; i<n; i++)
21         for(j=0; j<n; j++)
22         {
23             ans.mat[i][j]=0;
24             for(k=0; k<n; k++)
25                 ans.mat[i][j]=ans.mat[i][j]^(a.mat[i][k]*b.mat[k][j]);
26         }
27     return ans;
28 }
29 matrix add(matrix a ,matrix b,int n)
30 {
31     int i,j;
32     matrix ans;
33     for(i=0; i<n; i++)
34         for(j=0; j<n; j++)
35             ans.mat[i][j]=(a.mat[i][j]+b.mat[i][j])%mod;
36     return ans;
37 }
38 matrix powmod(matrix a,int m,int n)
39 {
40     matrix ans;
41     for(int i=0; i<n; i++)
42         for(int j=0; j<n; j++)
43             ans.mat[i][j]=(i==j);
44     while(m)
45     {
46         if(m&1)
47             ans=mult(ans,a,n);
48         a=mult(a,a,n);
49         m>>=1;
50     }
51     return ans;
52 }
53 matrix summod(matrix a,int k,int n)
54 {
55     if(k==1)    return a;
56     if(k&1) return add(powmod(a,k,n),summod(a,k-1,n),n);
57     else    return mult(add(E,powmod(a,k>>1,n),n),summod(a,k>>1,n),n);
58 }
59 void debug(matrix a,int len)
60 {
61     int i,j;
62     for(i=0;i<len;i++)
63     {
64         for(j=0;j<len;j++)
65             printf("%d",a.mat[i][j]);
66         puts("");
67     }
68 }
69 int main()
70 {
71     int t,i,j;
72     char s[110];
73     while(scanf("%d%s",&t,s)!=EOF)
74     {
75         int len=strlen(s);
76         memset(f.mat,0,sizeof(f.mat));
77         for(i=0;i<len;i++)
78         {
79                 f.mat[i][i]=f.mat[i][(i+1)%len]=1;
80                 B.mat[0][i]=s[i]-'0';
81         }
82         matrix ans=powmod(f,t,len);
83         //debug(ans,len);
84         //puts("");
85         //debug(B,len);
86         //ans=mult(B,ans,len);
87         for(i=0;i<len;i++)
88         {
89             int sum=0;
90             for(j=0;j<len;j++)
91                 sum=sum^(ans.mat[j][i]*B.mat[0][j]);
92             printf("%d",sum);
93         }
94         //for(i=0;i<len;i++)
95          //   printf("%d",ans.mat[0][i]);
96         puts("");
97     }
98     return 0;
99 }

View Code

http://acm.fzu.edu.cn/problem.php?pid=1683 fzu 1683 纪念slingshot

这题的构造方法跟上述第二题差不多，不同的是这题要求的是前n项的和，我们可以增加一维来表示和构造矩阵。。

3 2 7 0

1 0 0 0

0 1 0 0

3 2 7 1

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <queue>
 6 using namespace std;
 7 const int N = 4;
 8 const int mod =2009;
 9 #define ll long long
10 struct matrix
11 {
12     ll mat[N][N];
13 }f,E,b;
14 int a[5]={5,3,1,9};
15 matrix mult(matrix a,matrix b,int n)
16 {
17     int i,j,k;
18     matrix ans;
19     for(i=0;i<n;i++)
20         for(j=0;j<n;j++)
21         {
22             ans.mat[i][j]=0;
23             for(k=0;k<n;k++)
24                 ans.mat[i][j]=(ans.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod;
25         }
26     return ans;
27 }
28 matrix add(matrix a ,matrix b,int n)
29 {
30     int i,j;
31     matrix ans;
32     for(i=0;i<n;i++)
33         for(j=0;j<n;j++)
34             ans.mat[i][j]=(a.mat[i][j]+b.mat[i][j])%mod;
35     return ans;
36 }
37 matrix powmod(matrix a,int m,int n)
38 {
39     matrix ans;
40     for(int i=0;i<n;i++)
41         for(int j=0;j<n;j++)
42             ans.mat[i][j]=(i==j);
43     while(m)
44     {
45         if(m&1)
46             ans=mult(ans,a,n);
47         a=mult(a,a,n);
48         m>>=1;
49     }
50     return ans;
51 }
52 matrix summod(matrix a,int k,int n)
53 {
54     if(k==1)    return a;
55     if(k&1) return add(powmod(a,k,n),summod(a,k-1,n),n);
56     else    return mult(add(E,powmod(a,k>>1,n),n),summod(a,k>>1,n),n);
57 }
58 int main()
59 {
60     int t;
61     scanf("%d",&t);
62     for(int cas=1;cas<=t;cas++)
63     {
64         printf("Case %d: ",cas);
65         int n;
66         scanf("%d",&n);
67         if(n==0)
68         {
69             printf("%d
",1);
70             continue;
71         }
72         if(n==1)
73         {
74             printf("%d
",4);
75             continue;
76         }
77         if(n==2)
78         {
79             printf("%d
",9);
80             continue;
81         }
82         f.mat[0][0]=3,f.mat[0][1]=2,f.mat[0][2]=7,f.mat[0][3]=0;
83         f.mat[1][0]=1,f.mat[1][1]=0,f.mat[1][2]=0,f.mat[1][3]=0;
84         f.mat[2][0]=0,f.mat[2][1]=1,f.mat[2][2]=0,f.mat[2][3]=0;
85         f.mat[3][0]=3,f.mat[3][1]=2,f.mat[3][2]=7,f.mat[3][3]=1;
86         matrix ans=powmod(f,n-2,4);
87         int sum=0;
88         for(int i=0;i<4;i++)
89             sum=(sum+ans.mat[3][i]*a[i])%mod;
90         printf("%d
",sum);
91     }
92     return 0;
93 }

View Code

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3497 ZOJ 3497 Mistwald

这题。。。还记得当初做的时候以为是个搜索。。不会做，现在发现原来直接可以通过矩阵来解决。。好强大

对每个点与其可通向的四个方向点进行连边，都是单向的。。最后一点除外，然后就是个可达矩阵了。。然后

K次方运算，如果不可达，则false，如果k次只能到达终点，则true，否则maybe//

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <queue>
  6 using namespace std;
  7 const int N = 6;
  8 //const int mod =1000;
  9 #define ll long long
 10 struct matrix
 11 {
 12     int mat[N*N][N*N];
 13 }f,E;
 14 matrix mult(matrix a,matrix b,int n)
 15 {
 16     int i,j,k;
 17     matrix ans;
 18     for(i=0;i<n;i++)
 19         for(j=0;j<n;j++)
 20         {
 21             ans.mat[i][j]=0;
 22             for(k=0;k<n;k++)
 23                 ans.mat[i][j]=(ans.mat[i][j]+a.mat[i][k]*b.mat[k][j]);
 24         }
 25     return ans;
 26 }
 27 matrix add(matrix a ,matrix b,int n)
 28 {
 29     int i,j;
 30     matrix ans;
 31     for(i=0;i<n;i++)
 32         for(j=0;j<n;j++)
 33             ans.mat[i][j]=(a.mat[i][j]+b.mat[i][j]);
 34     return ans;
 35 }
 36 matrix powmod(matrix a,int m,int n)
 37 {
 38     matrix ans;
 39     for(int i=0;i<n;i++)
 40         for(int j=0;j<n;j++)
 41             ans.mat[i][j]=(i==j);
 42     while(m)
 43     {
 44         if(m&1)
 45             ans=mult(ans,a,n);
 46         a=mult(a,a,n);
 47         m>>=1;
 48     }
 49     return ans;
 50 }
 51 matrix summod(matrix a,int k,int n)
 52 {
 53     if(k==1)    return a;
 54     if(k&1) return add(powmod(a,k,n),summod(a,k-1,n),n);
 55     else    return mult(add(E,powmod(a,k>>1,n),n),summod(a,k>>1,n),n);
 56 }
 57 int main()
 58 {
 59     int t,i,j,m,n;
 60     scanf("%d",&t);
 61     while(t--)
 62     {
 63         memset(f.mat,0,sizeof(f.mat));
 64         int x1,y1,x2,y2,x3,y3,x4,y4;
 65         scanf("%d%d",&m,&n);
 66         for(i=0;i<m;i++)
 67         {
 68             for(j=0;j<n;j++)
 69             {
 70                 getchar();
 71                 scanf("((%d,%d),(%d,%d),(%d,%d),(%d,%d))",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
 72                 if(i==m-1&&j==n-1)  continue;
 73                 f.mat[i*n+j][(x1-1)*n+y1-1]=1;
 74                 f.mat[i*n+j][(x2-1)*n+y2-1]=1;
 75                 f.mat[i*n+j][(x3-1)*n+y3-1]=1;
 76                 f.mat[i*n+j][(x4-1)*n+y4-1]=1;
 77             }
 78         }
 79         int q,p;
 80         scanf("%d",&q);
 81         while(q--)
 82         {
 83             scanf("%d",&p);
 84             matrix ans=powmod(f,p,n*m);
 85             if(ans.mat[0][n*m-1]==0)
 86             {
 87                 printf("False
");
 88                 continue;
 89             }
 90             for(i=0;i<n*m-1;i++)
 91                 if(ans.mat[0][i])
 92                     break;
 93             if(i==n*m-1)
 94                 printf("True
");
 95             else
 96                 printf("Maybe
");
 97         }
 98         puts("");
 99     }
100     return 0;
101 }

View Code

还有一些矩阵的题，有兴趣可以做做：

http://acm.hdu.edu.cn/showproblem.php?pid=3117 这题求后四位直接矩阵就可以了，主要是学习一下前位的求法。另，fib也是有循环节的= =

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2853

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2974

http://acm.hdu.edu.cn/showproblem.php?pid=2855 一个很牛x的推公式orz

http://acm.hdu.edu.cn/showproblem.php?pid=3483 也是神构造。。

http://acm.hdu.edu.cn/showproblem.php?pid=2807 和最短路的结合//