牛客第二场 E MAZE —— 线段树 + 矩阵

本文主要是介绍牛客第二场 E MAZE —— 线段树 + 矩阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    一张 $n\times m$ 的图，$0$ 表示可走， $1$ 不可走
    只能向下、左右走，不能回走
    多次查询，两种操作：
    将某个位置反转
    问从第一行 $a_i$ 到第 $n$ 行 $b_i$ 的的方案数

解题思路：

    $dp[i][j]=sum(dp[i-1][k]$ for $(k<j$ and $b_{ik}=b_{ik+1}=...=b_{ij}=0))+$
                       $sum(dp[i-1][k]$ for $(k>j$ and $b_{ik}=b_{ik-1}=...=b_{ij}=0))$

    所以相邻两行就可以用矩阵相乘计算
    然后用线段树维护
    每个节点表示一段区间的系数转移矩阵
    时间复杂度：$O(q{m}^{3}logn)$
    详细可看：这里

核心：线段树维护系数矩阵

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const ll mod = 1e9 + 7;
const int maxn = 5e4 + 5;
int n, m, q, op;
int b[maxn][15];
struct node{ll s[15][15];void init() {memset(s, 0, sizeof(s));}node operator + (const node &a) const {node ret; ret.init();for(int i=1; i<=m; i++)for(int j=1; j<=m; j++)for(int k=1; k<=m; k++)ret.s[i][j] = (ret.s[i][j]+s[i][k]*a.s[k][j]%mod) % mod;return ret;}
} t[maxn<<2];  void get(node &h, int r){h.init();for(int i=1; i<=m; i++)if(!b[r][i]){h.s[i][i] = 1;for(int j=i-1; j && !b[r][j]; j--) h.s[j][i] = 1;for(int j=i+1; j<=m && !b[r][j]; j++) h.s[j][i] = 1;}
}void build(int l, int r, int rt){if(l == r){get(t[rt], l);return;}int m = l + r >> 1;build(l, m, rt<<1);build(m+1, r, rt<<1|1);t[rt] = t[rt<<1] + t[rt<<1|1];
}
void update(int pos, int l, int r, int rt){if(l>pos || r<pos) return;if(l == r){get(t[rt], l);return;}int m = l + r >> 1;update(pos, l, m, rt<<1);update(pos, m+1, r, rt<<1|1);t[rt] = t[rt<<1] + t[rt<<1|1];
}
int main() {scanf("%d%d%d", &n, &m, &q);for(int i=1; i<=n; i++){char s[15];scanf("%s", s+1);for(int j=1; j<=m; j++)if(s[j]=='1') b[i][j] = 1;}build(1, n, 1);while(q--){int u, v;scanf("%d%d%d", &op, &u, &v);if(op & 1) b[u][v] ^= 1, update(u, 1, n, 1);else printf("%d\n", t[1].s[u][v]);}
}

这篇关于牛客第二场 E MAZE —— 线段树 + 矩阵的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---