线性变换与矩阵递推习题：hdu 5068 Harry And Math Teacher

题目描述

有$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$

一段区间内的方案数是区间内矩阵相乘后的矩阵行列值求和

线段树维护区间矩阵乘积

代码

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