首页 > 代码库 > HDU 5068 Harry And Math Teacher 线段树+矩阵乘法
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 Phantom01117 freopen("1003.txt", "r", stdin);118 #endif //Phantom01119 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\n", 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 }
HDU 5068 Harry And Math Teacher 线段树+矩阵乘法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。