盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

HDU 5058 Harry And Math Teacher(dp+矩阵+线段树)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5058

题意

有n层楼,每一层有两扇门。从第i层楼到第i+1层楼有4条路,即从i层的每扇门到i+1层的每扇门都有一条路。现在有两种操作,一种是将第i层到第i+1层的某条路给干掉(或者重新修好)。另一种是询问从第i层到第j层有多少不同的路。

思路

假设到第i层的第一扇门为dp[i][1]种,第二扇们有dp[i][2]中。那么
dp[i + 1][1] = a1 dp[i][1] + a2 dp[i][2]
dp[i + 1][2] = b1 dp[i][2] + b2 dp[i][2]
所以就相当于从第i层到第i+1层只需要乘以一个转换矩阵即可。而一开始转换矩阵中元素都为1。当有一条路被干掉则变为0
于是这道题就变成线段树维护矩阵乘积,单点更新,区间求乘积

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define debug puts("=====================");
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
typedef long long ll;
int n, m;
const int N = 50000 + 100;
const ll mod = 1000000007;
struct node {
ll a[2][2];
void clr() {
memset(a, 0, sizeof(a));
}
void uni() {
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++) a[i][j] = 1;
}
void one() {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) a[i][j] = 0;
a[i][i] = 1;
}
}
void out() {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) cout<<a[i][j]<<" ";
cout<<endl;
}
}
ll get() {
ll ans = 0;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++) ans += a[i][j], ans %= mod;
return ans;
}
node operator * (const node & T) {
node tmp;
memset(tmp.a, 0, sizeof(tmp.a));
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
tmp.a[i][j] += a[i][k] * T.a[k][j], tmp.a[i][j] %= mod;
return tmp;
}
}mul[N << 2], tmp;
void pushup(int rt) {
mul[rt].clr();
mul[rt] = mul[rt << 1] * mul[rt << 1 | 1];
}
void build(int l, int r, int rt) {
if (l == r) {
mul[rt].uni();
return ;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushup(rt);
}
void update(int L, int R, int y, int z, int l, int r, int rt) {
if (L <= l && r <= R) {
mul[rt].a[y][z] ^= 1;
//mul[rt].out();
return ;
}
int m = (l + r) >> 1;
if (L <= m) update(L, R, y, z, lson);
if (R > m) update(L, R, y, z, rson);
pushup(rt);
}
node query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
return mul[rt];
}
int m = (l + r) >> 1;
node ret;
ret.one();
if (L <= m) ret = ret * query(L, R, lson);
if (R > m) ret = ret * query(L, R, rson);
return ret;
}
int main () {
int op, a, b, x, y, z;
while(~scanf("%d%d", &n, &m)) {
n--;
build(1, n, 1);
while(m--) {
scanf("%d", &op);
if (op == 0) {
scanf("%d%d", &a, &b);
tmp = query(a, b - 1, 1, n, 1);
printf("%I64d\n", tmp.get());
} else {
scanf("%d%d%d", &x, &y, &z);
if (y == 1 && z == 1) y = 0, z = 0;
else if (y == 1 && z == 2) y = 0, z = 1;
else if (y == 2 && z == 1) y = 1, z = 0;
else y = 1, z = 1;
update(x, x, y, z, 1, n, 1);
}
}
}
return 0;
}

更新日志

  • 14562794 2015-08-18 21:47:28 Accepted 5068 795MS 5688K 2508 B G++ SIO__Five