zoj - 3538（矩阵乘法）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long LL;
 7 const LL mod = 1000000007;
 8 struct Z{
 9     LL m[2][2];
10     LL a;
11     string b;
12 }s[20];
13 Z A ={
14     -1,0,
15     3,3
16 };
17 Z B = {
18     1,0,
19     0,1
20 };
21 LL Pow(LL a,LL b){
22     LL res = 1;
23     while(b){
24         if(b&1) res = res * a % mod ;
25         a = a * a % mod;
26         b >>= 1;
27     }
28     return res;
29 }
30 bool cmp(Z p,Z q){
31     return p.a < q.a;
32 }
33 Z operator * (const Z& a,const Z& b){
34     Z c;
35     for(int i = 0;i < 2 ; ++ i)
36         for(int j = 0;j < 2;j++){
37             c.m[i][j] = 0;
38             for(int k = 0;k < 2;k++)
39                 c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
40         }
41     return c;
42 }
43 Z mpow(int n){
44     Z ret , p;
45     ret = B, p = A;
46     while(n){
47         if(n&1) ret = ret * p;
48         p = p * p;
49         n >>= 1;
50     }
51     return ret;
52 }
53 int main(){
54     LL n,m,flag = 0;;
55     while(cin>>n>>m){
56         if(m == 0){
57             LL x = 4 * Pow(3,n-1) % mod;
58             cout << x << endl;
59             continue;
60         }
61         for(int i = 1;i <= m;i++)
62             cin>>s[i].a>>s[i].b;
63 
64         if(m == 1){
65             LL x = Pow(3,n-1);
66             cout << x << endl;
67             continue;
68         }
69         sort(s+1,s+m+1,cmp);
70         LL x = 1;
71         Z ant;
72         s[0].a = 0;
73         for(int i = 1;i <= m; ++ i){
74 
75             if(s[i-1].a != 0){
76                 LL abs = s[i].a - s[i-1].a - 2;
77                 if(abs < 0)
78                 {
79                     if(s[i-1].b[0] == s[i].b[0]) {x = 0;break;}
80                     continue;
81                 }
82                 ant = mpow(abs);
83                 if(s[i-1].b[0] == s[i].b[0])
84                    x = x * (ant.m[0][0]*3 + ant.m[1][0]*3)%mod;
85                 else x = x * (ant.m[0][0]*2 + ant.m[1][0]*3)%mod;
86 
87             }
88             else {
89                 x = x * Pow(3,s[i].a - 1) % mod;
90             }
91             if(i == m && s[i].a < n){
92                 x = x * Pow(3,n-s[i].a) % mod;
93             }
94         }
95         cout << (x%mod + mod)%mod<< endl;
96     }
97 }