E-MAZE

思路：

借鉴某位大佬博客，很详细：点击
这是一个进阶版的走网格，现在是从上面往左右或者下方走，而且起点和终点是不固定，但起点和终点所在的行数是固定的，同时，还有一些地方是不能走的。
我们主要考虑行与行之间的关系，很明显，下一行的某个位置子肯定是由上一行的一些位置走过有来的。
假设第行的情况为：

那么状态转移方程:(先大概了解下就行，最右边的矩阵是到的转移矩阵)

举例子：
表示的是从起点到蓝色格子的方案数，看下图就能发现，它的值就是(假设不是第一行)前面所有路径经过绿色格子然后经过到达蓝色格子的方案数。(之所以用矩阵求，就是因为第行可以由第行线性表示，这种情况一般会用到矩阵)

由矩阵相乘的性质，可以求出第行转移矩阵的第列为：

其它列同理，接着求其它列，进而求出第行的转移矩阵，其它行的转移矩阵同理可求。

由的定义可以知道，第一行只有起点的值是，其它的是；假设终点为，答案即为，(注意为经过到达的路径数，而不是)

假设为第行的转移矩阵，那么：

计算之后发现答案就是所有转移矩阵相乘后的值，分别是起点和终点。

每求一次答案的复杂度是，如果求次复杂度就是了，可以考虑用把每个矩阵看成一个点，用线段树维护区间乘积可以降到，仅涉及到线段树的单点修改，由线段树的性质可知查询整个区间的乘积是的。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e4+7,mod=1e9+7;
typedef long long int ll;
int n,m;
struct node {
    ll mat[12][12];
    node() {
        memset(mat,0,sizeof mat);
    }
    node operator*(node other) {
        node res;
        for(int i=1; i<=m; ++i)
            for(int j=1; j<=m; ++j)
                for(int k=1; k<=m; ++k) {
                    res.mat[i][j]+=mat[i][k]*other.mat[k][j];
                    res.mat[i][j]%=mod;
                }
        return res;
    }
} tree[maxn<<2];
bool mp[maxn][12];
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline void build(int l,int r,int rt) {
    if(l==r) {
        for(int j=1; j<=m; ++j) {
            if(mp[l][j]) continue;
            for(int i=j; i<=m; ++i) {
                if(mp[l][i]) break;
                tree[rt].mat[i][j]=1;
            }//转移矩阵第i行第j列
            for(int i=j-1; i; --i) {
                if(mp[l][i]) break;
                tree[rt].mat[i][j]=1;
            }
        }//转移矩阵第j列
        return;
    }//第l行的转移矩阵
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    tree[rt]=tree[rt<<1]*tree[rt<<1|1];
}
inline void update(int x,int l,int r,int rt) {
    if(l==r) {
        memset(tree[rt].mat,0,sizeof tree[rt].mat);
        for(int j=1; j<=m; ++j) {
            if(mp[l][j]) continue;
            for(int i=j; i<=m; ++i) {
                if(mp[l][i]) break;
                tree[rt].mat[i][j]=1;
            }//转移矩阵第i行第j列
            for(int i=j-1; i; --i) {
                if(mp[l][i]) break;
                tree[rt].mat[i][j]=1;
            }
        }//转移矩阵第j列
        return;
    }//第l行的转移矩阵
    int mid=(l+r)>>1;
    if(x<=mid) update(x,lson);
    else update(x,rson);
    tree[rt]=tree[rt<<1]*tree[rt<<1|1];
}
int main() {
    int q,a,b,Q;
    scanf("%d%d%d",&n,&m,&Q);
    for(int i=1,j; i<=n; ++i)
        for(j=1; j<=m; ++j) scanf("%1d",&mp[i][j]);
    build(1,n,1);
    while(Q--) {
        scanf("%d%d%d",&q,&a,&b);
        if(q&1) {
            mp[a][b]^=1;
            update(a,1,n,1);
        } else printf("%lld\n",tree[1].mat[a][b]);
    }
}