首页 > 代码库 > HDU 5068 Harry And Math Teacher（ 矩阵乘法 + 线段树维护 ）
HDU 5068 Harry And Math Teacher（ 矩阵乘法 + 线段树维护 ）
HDU 5068 Harry And Math Teacher（ 矩阵乘法 + 线段树维护 ）
题意:首先是这题题意理解错误，，其次是这题无法理解状态。。。已经不是英文有多烂的情况了，是中文没学好啊。。。。。大学不学语文才是真正的硬伤啊题目意思 有一个城堡有很多层楼， 每层楼有2个门，每个门里面又有两个楼梯，可以通往上一层的两个门问，从x层楼到y层楼有多少中方法（不能返回）
具体看图吧，，，已经不会说话了
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <vector> 5 #include <list> 6 #include <queue> 7 #include <map> 8 #include <set> 9 #include <algorithm> 10 #include <cmath> 11 #include <ctime> 12 using namespace std; 13 typedef long long LL; 14 typedef unsigned long long ULL; 15 #define CLR(a,b) memset( a, b, sizeof(a) ) 16 #define REP(i,a,b) for( int i = a; i < b; ++i ) 17 #define FOR(i,a,b) for( int i = a; i <= b; ++i ) 18 #define FOD(i,a,b) for( int i = a; i >= b; --i ) 19 20 const int MAX_SIZE = 2; 21 const int MAXN = 50005; 22 const int MOD = 1000000007; 23 #define lson l, m, o << 1 24 #define rson m + 1, r, o << 1 | 1 25 #define ls o << 1 26 #define rs o << 1 | 1 27 28 inline void scan( int &x ) 29 { 30 char c; 31 while( c = getchar(), c < ‘0‘ || c >‘9‘ ); 32 x = c - ‘0‘; 33 while( c = getchar(), c >=‘0‘ && c <= ‘9‘ ) x = x*10 + c - ‘0‘; 34 } 35 36 struct Matrix 37 { 38 LL matrix[MAX_SIZE][MAX_SIZE]; 39 int n; 40 41 Matrix(int _n=2) : n(_n) {} 42 void clear() 43 { 44 CLR(matrix,0); 45 } 46 void init() 47 { 48 REP(i,0,n) 49 REP(j,0,n) 50 matrix[i][j] = (i == j); 51 } 52 Matrix operator * (const Matrix &a) const 53 { 54 Matrix c(n); 55 c.clear(); 56 REP(i,0,n) 57 REP(j,0,n) 58 REP(k,0,n) 59 c.matrix[i][j] = (c.matrix[i][j] + matrix[i][k]* a.matrix[k][j]) % MOD; 60 return c; 61 } 62 }; 63 64 Matrix Tree[MAXN << 2]; 65 66 inline void push_up( int o ) 67 { 68 Tree[o] = Tree[ls] * Tree[rs]; 69 } 70 71 void build( int l, int r, int o ) 72 { 73 if( l == r ) 74 { 75 for( int i = 0; i < 2; ++i ) 76 for( int j = 0; j < 2; ++j ) 77 Tree[o].matrix[i][j] = 1; 78 return; 79 } 80 int m = ( l + r ) >> 1; 81 build( lson ); 82 build( rson ); 83 push_up( o ); 84 } 85 86 void update( int x, int y, int z, int l, int r, int o ) 87 { 88 if( l == r ) 89 { 90 Tree[o].matrix[y][z] ^= 1; 91 return; 92 } 93 int m = ( l + r ) >> 1; 94 if( x <= m ) update( x, y, z, lson ); 95 else update( x, y, z, rson ); 96 push_up( o ); 97 } 98 99 Matrix query( int L, int R, int l, int r, int o )100 {101 if( L == l && R == r )102 return Tree[o];103 int m = ( l + r ) >> 1;104 if( R <= m ) return query( L, R, lson );105 else if( L > m ) return query( L, R, rson );106 else107 {108 return query( L, m, lson) * query( m+1, R, rson );109 }110 }111 112 void Orz()113 {114 int m, n;115 while( ~scanf( "%d %d", &n, &m ) )116 {117 build( 1, n - 1, 1 );118 while( m-- )119 {120 int op, x, y, z;121 scan( op ); scan( x ); scan( y );122 if( op == 0 )123 {124 Matrix res;125 res = query( x, y - 1, 1, n - 1, 1 );126 printf( "%I64d\n", ( res.matrix[0][0] + res.matrix[0][1] + res.matrix[1][0] + res.matrix[1][1] ) % MOD );127 }128 else 129 {130 scan( z );131 update( x, y - 1, z - 1, 1, n - 1, 1 );132 }133 }134 }135 }136 137 int main()138 {139 Orz(); 140 return 0;141 }
HDU 5068 Harry And Math Teacher（ 矩阵乘法 + 线段树维护 ）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。