zoj 2671 Cryptography（矩阵+线段树）

题意：给出n个2*2的矩阵，有m个查询，问某段区间的矩阵乘积。
由于矩阵乘积符合结合律，故可用线段树来完成。
View Code
 1 /*
 2 Author:Zhaofa Fang
 3 Lang:C++
 4 */
 5 #include <cstdio>
 6 #include <cstdlib>
 7 #include <iostream>
 8 #include <cmath>
 9 #include <cstring>
10 #include <algorithm>
11 #include <string>
12 #include <vector>
13 #include <queue>
14 #include <stack>
15 #include <map>
16 #include <set>
17 using namespace std;
18 
19 typedef long long ll;
20 const int INF = 2147483647;
21 
22 /*
23     a b
24     c d
25 */
26 #define lson l , m , rt << 1
27 #define rson m + 1 , r , rt << 1 | 1
28 
29 struct Ma
30 {
31     int a,b,c,d;
32 }f[30005];
33 
34 int N,M,R;
35 Ma product(Ma A,Ma B)
36 {
37     Ma ret;
38     ret.a = (A.a*B.a+A.b*B.c)%R;
39     ret.b = (A.a*B.b+A.b*B.d)%R;
40     ret.c = (A.c*B.a+A.d*B.c)%R;
41     ret.d = (A.c*B.b+A.d*B.d)%R;
42     return ret;
43 }
44 Ma sum[30005<<2];
45 void PushUp(int rt)
46 {
47     sum[rt] = product(sum[rt<<1],sum[rt<<1|1]);
48 }
49 void build(int l,int r,int rt)
50 {
51     if(l == r)
52     {
53         scanf("%d%d%d%d",&sum[rt].a,&sum[rt].b,&sum[rt].c,&sum[rt].d);
54         return ;
55     }
56     int m = (l + r) >> 1;
57     build(lson);
58     build(rson);
59     PushUp(rt);
60 }
61 Ma query(int L,int R,int l,int r,int rt)
62 {
63     if(L <= l && r <= R)
64     {
65         return sum[rt];
66     }
67     int m = (l + r) >> 1;
68     Ma ret={1,0,0,1};
69     if(L <= m)ret = product(ret,query(L,R,lson));
70     if(m < R)ret = product(ret,query(L,R,rson));
71     return ret;
72 }
73 int main()
74 {
75  //   freopen("in","r",stdin);
76     bool flag=0;
77     while(~scanf("%d%d%d",&R,&N,&M))
78     {
79         build(1,N,1);
80         while(M--)
81         {
82             if(flag)puts("");
83             else flag=1;
84             int u,v;
85             scanf("%d%d",&u,&v);
86             Ma ret=query(u,v,1,N,1);
87             printf("%d %d\n%d %d\n",ret.a,ret.b,ret.c,ret.d);
88         }
89     }
90     return 0;
91 }
by Farmer