线性变换与矩阵递推习题：hdu 6155 Subsequence Count

题目描述

给定一个长度为$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}
$$

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

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

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

代码

#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();
}