HDU 5068 Harry And Math Teacher 线段树+矩阵乘法

题意：

　　一栋楼有n层，每一层有2个门，每层的两个门和下一层之间的两个门之间各有一条路(共4条)。

　　有两种操作：

　　0 x y : 输出第x层到第y层的路径数量。

　　1 x y z : 改变第x层的 y门到第x+1层的 z门的通断情况。

思路：

　　门之间的路径数可以用矩阵来表示，经过的中间层可以用矩阵乘积表示。所以用线段树维护矩阵乘积即可。

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <algorithm>
  7 #include <string>
  8 #include <queue>
  9 #include <stack>
 10 #include <vector>
 11 #include <map>
 12 #include <set>
 13 #include <functional>
 14 #include <cctype>
 15 #include <time.h>
 16 
 17 using namespace std;
 18 
 19 typedef __int64 ll;
 20 
 21 const int INF = 1<<30;
 22 const int MAXN = 5e4+55;
 23 const ll MOD = 1e9+7;
 24 
 25 struct Matrix {
 26     ll a[2][2];
 27 
 28     Matrix() {}
 29 
 30     Matrix(int x) {
 31         for (int i = 0; i < 2; i++)
 32             for (int j = 0; j < 2; j++)
 33                 a[i][j] = i==j ? x : 0;
 34     }
 35 
 36     Matrix operator * (const Matrix &x) {
 37         Matrix res;
 38         for (int i = 0; i < 2; i ++) {
 39             for (int j = 0; j < 2; j++) {
 40                 res.a[i][j] = 0;
 41                 for (int k = 0; k < 2; k++) {
 42                     res.a[i][j] = (res.a[i][j]+a[i][k]*x.a[k][j])%MOD;
 43                 }
 44             }
 45         }
 46         return res;
 47     }
 48 
 49     inline ll sum() {
 50         return (a[0][0] + a[0][1] + a[1][0] + a[1][1])%MOD;
 51     }
 52 
 53     inline void update(int i, int j) {
 54         a[i][j] ^= 1;
 55     }
 56 
 57     inline void init() {
 58         a[0][0] = a[0][1] = a[1][0] = a[1][1] = 1;
 59     }
 60     void output() {
 61         puts("Matrix: ");
 62         for (int i = 0; i < 2; i ++) {
 63             for (int j = 0; j < 2; j++)
 64                 printf("%I64d ", a[i][j]);
 65             puts("");
 66         }
 67     }
 68 };
 69 
 70 Matrix a[MAXN<<2];
 71 int id[MAXN];
 72 
 73 #define LS l, m, p<<1
 74 #define RS m+1, r, p<<1|1
 75 
 76 inline void pushUp(int p) {
 77     a[p] = a[p<<1]*a[p<<1|1];
 78 }
 79 
 80 void build(int l, int r, int p) {
 81     if (l==r) {
 82         a[p].init();
 83         id[l] = p;
 84         return ;
 85     }
 86     int m = (l+r) >> 1;
 87     build(LS);
 88     build(RS);
 89     pushUp(p);
 90 }
 91 
 92 void update(int p, int i, int j) {
 93     p = id[p];
 94     a[p].update(i, j);
 95     p >>= 1;
 96     while (p>0) {
 97         pushUp(p);
 98         p >>= 1;
 99     }
100 }
101 
102 Matrix query(int L, int R, int l, int r, int p) {
103     if (L<=l&&r<=R)
104         return a[p];
105 
106     int m = (l+r)>>1;
107 
108     Matrix res(1);
109     if (L<=m) res = res * query(L, R, LS);
110     if (m <R) res = res * query(L, R, RS);
111 
112     return res;
113 }
114 
115 int main() {
116     #ifdef Phantom01
117         freopen("1003.txt", "r", stdin);
118     #endif //Phantom01
119 
120     int n, m;
121     int op, x, y, z;
122     while (scanf("%d%d", &n, &m)!=EOF) {
123         n--;
124         build(1, n, 1);
125         while (m--) {
126             scanf("%d", &op);
127             if (op==0) {
128                 scanf("%d%d", &x, &y);
129                 y--;
130                 printf("%I64d
", query(x, y, 1, n, 1).sum());
131             } else {
132                 scanf("%d%d%d", &x, &y, &z);
133                 y--; z--;
134                 update(x, y, z);
135             }
136         }
137     }
138 
139     return 0;
140 }

View Code