题目描述

有$n$层楼,每层楼有两个楼梯(编号为$0$和$1$),初始的时候第$i$层和第$i+1$层楼的楼梯两两可达

有若干次操作,诸如

  1. 将第$i$层的第$x$号楼梯和第$i+1$层的第$y$号楼梯的连通性反转
  2. 查询从第$x$层到第$y$层的方案数(只能上楼,不能下楼)

题解

设$f_{i,j}$表示到达第$i$层第$j$个楼梯的方案数

$$
\begin{cases}
f_{i,0}=a_{0,0} \times f_{i-1,0}+a_{0,1} \times f_{i-1,1} \\
f_{i,1}=a_{1,0} \times f_{i-1,0}+a_{1,1} \times f_{i-1,1}
\end{cases}
$$

然后写成矩阵递推

$$
\begin{pmatrix}
f_{i-1,0} & f_{i-1,1}
\end{pmatrix}
\begin{pmatrix}
a_{0,0} & a_{1,0} \\
a_{0,1} & a_{1,1}
\end{pmatrix}
=
\begin{pmatrix}
f_{i,0} & f_{i,1}
\end{pmatrix}
$$

那么只需要维护是否相邻的矩阵即可

初始矩阵全部联通都为$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
#include "bits/stdc++.h"
using namespace std;
const int N = 5e4 + 10, p = 1e9 + 7;
typedef long long ll;

struct Mat {
ll a[2][2];
Mat() { memset(a, 0, sizeof a); }
ll* operator [] (int i) { return a[i]; }
Mat operator * (Mat b) {
Mat rs;
for(int i = 0 ; i < 2 ; ++ i)
for(int j = 0 ; j < 2 ; ++ j)
for(int k = 0 ; k < 2 ; ++ k)
rs[i][j] = (rs[i][j] + a[i][k] * b[k][j]) % p;
return rs;
}
} mat[N * 4];

int n, m;

#define lc (id << 1)
#define rc (id << 1 | 1)

void update(int id) { mat[id] = mat[lc] * mat[rc]; }

void build(int id, int l, int r) {
int mid = (l + r) >> 1;
if(l == r) mat[id][0][0] = mat[id][0][1] = mat[id][1][0] = mat[id][1][1] = 1;
else build(lc, l, mid), build(rc, mid + 1, r), update(id);
}

void modify(int id, int l, int r, int pos, int x, int y) {
int mid = (l + r) >> 1;
if(l == r) return mat[id][x][y] ^= 1, void();
if(pos <= mid) modify(lc, l, mid, pos, x, y);
else modify(rc, mid + 1, r, pos, x, y); update(id);
}

Mat query(int id, int l, int r, int ql, int qr) {
int mid = (l + r) >> 1;
if(ql <= l && r <= qr) return mat[id];
else if(qr <= mid) return query(lc, l, mid, ql, qr);
else if(ql >= mid + 1) return query(rc, mid + 1, r, ql, qr);
else return query(lc, l, mid, ql, mid) * query(rc, mid + 1, r, mid + 1, qr);
}

void sol() {
memset(mat, 0, sizeof mat);
build(1, 1, n);
for(int i = 1, op, l, r, pos, x, y ; i <= m ; ++ i) {
scanf("%d", &op);
if(op == 0) {
scanf("%d%d", &l, &r);
Mat t = query(1, 1, n, l, r - 1);
ll rs = 0;
for(int i = 0 ; i < 2 ; ++ i) for(int j = 0 ; j < 2 ; ++ j) rs = (rs + t[i][j]) % p;
printf("%lld\n", rs);
} else {
scanf("%d%d%d", &pos, &x, &y);
modify(1, 1, n, pos, x - 1, y - 1);
}
}
}

int main() {
while(scanf("%d%d", &n, &m) == 2) sol();
}