题目描述

给定一个长度为$n$的$01$序列,支持两种操作

  1. $\forall i \in [l,r] \cap Z,s_i \leftarrow 1 - s_i$
  2. 查询$s[l \dots r]$中本质不同的子序列个数

题解

先想想如何求一个$01$序列中的本质不同的子序列的个数

设$f_{i,j}$表示$s[1 \dots i]$中,结尾为$j$的本质不同的子序列的个数,其中$i \in [l,r] \cap Z \wedge j \in \\{ 0,1 \\}$

那么有以下转移方程

$$
\begin{cases}
\begin{cases}
f_{i,0} = f_{i-1,0}+f_{i-1,1} + 1 \\
f_{i,1}=f_{i-1,1}
\end{cases}
& \qquad s_i=0 \\
\begin{cases}
f_{i,0}=f_{i-1,0} \\
f_{i,1}=f_{i-1,0}+f_{i-1,1}+1
\end{cases}
& \qquad s_i=1
\end{cases}
$$

转移的含义?

以$s_i=0$为例:新增加一个子序列,以及之前的所有不同的子序列的末尾都增加一个$0$

写成矩阵转移形式

$$
\begin{cases}
\begin{pmatrix}
f_{i,0} & f_{i,1} & 1
\end{pmatrix}
\begin{pmatrix}
1 & 0 & 0 \\
1 & 1 & 0 \\
1 & 0 & 1
\end{pmatrix}
=
\begin{pmatrix}
f_{i+1,0} & f_{i+1,1} & 1
\end{pmatrix}
& s_i=0 \\
\begin{pmatrix}
f_{i,0} & f_{i,1} & 1
\end{pmatrix}
\begin{pmatrix}
1 & 1 & 0 \\
0 & 1 & 0 \\
0 & 1 & 1
\end{pmatrix}
=
\begin{pmatrix}
f_{i+1,0} & f_{i+1,1} & 1
\end{pmatrix}
& s_i=1
\end{cases}
$$

这两个转移矩阵可以相互转换的:第一行和第二行交换,然后第一列和第二列交换

之后可以通过线段树维护矩阵,并且打上反转标记实现区间反转的操作(证明略,可以大力展开矩阵乘法来证明)

区间查询的话就是维护矩阵的乘积

代码

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
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, p = 1e9 + 7;

struct Mat {
ll a[3][3];
Mat() { memset(a, 0, sizeof a); }
ll* operator [] (int i) { return a[i]; }
Mat operator * (Mat b) {
Mat c;
for(int i = 0 ; i < 3 ; ++ i)
for(int j = 0 ; j < 3 ; ++ j)
for(int k = 0 ; k < 3 ; ++ k)
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % p;
return c;
}
void output() {
puts("");
for(int i = 0 ; i < 3 ; ++ i, puts(""))
for(int j = 0 ; j < 3 ; ++ j)
printf("%lld ", a[i][j]);
puts("");
}
} mat[N * 10], I, M0, M1;

char s[N];
int rev[N * 10], n, m;

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

void push(int id) {
if(rev[id]) {
rev[lc] ^= 1, rev[rc] ^= 1, rev[id] = 0;
for(int i = 0 ; i < 3 ; ++ i) swap(mat[id][i][0], mat[id][i][1]);
for(int i = 0 ; i < 3 ; ++ i) swap(mat[id][0][i], mat[id][1][i]);
}
}

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

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

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

void modify(int id, int l, int r, int ql, int qr) {
int mid = (l + r) >> 1;
push(id);
if(ql > r || qr < l) return ;
else if(ql <= l && r <= qr) rev[id] ^= 1;
else modify(lc, l, mid, ql, qr), modify(rc, mid + 1, r, ql, qr), update(id);
}

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

int main() {
I[0][0] = 1, I[0][1] = 0, I[0][2] = 0;
I[1][0] = 0, I[1][1] = 1, I[1][2] = 0;
I[2][0] = 0, I[2][1] = 0, I[2][2] = 1;

M0[0][0] = 1, M0[0][1] = 0, M0[0][2] = 0;
M0[1][0] = 1, M0[1][1] = 1, M0[1][2] = 0;
M0[2][0] = 1, M0[2][1] = 0, M0[2][2] = 1;

M1[0][0] = 1, M1[0][1] = 1, M1[0][2] = 0;
M1[1][0] = 0, M1[1][1] = 1, M1[1][2] = 0;
M1[2][0] = 0, M1[2][1] = 1, M1[2][2] = 1;

int T; scanf("%d", &T);
while(T --) sol();
}