题意：
n * m的矩阵，为0表示可以走，1不可以走。规定每走一步只能向下、向左、向右走。现给定两种操作：
一.1 x y表示翻转坐标（x，y）的0、1。 二.2 x y表示从（1，x）走到（n，y）有几种走法思路：
假设\(dp[i][j]\)表示从下一层能到达（i，j）点的路径数，那么显然到达（i，j）的路径数为\(dp[i + 1][j]\)。
我们能很显然的得到转移方程\(dp[i][j] = \sum_{k = l}^r dp[i - 1][k]\)，其中l~r为（i，j）下方能直接走到（i，j）的连续区间。 我们可以直接用矩阵维护这个转移方程：\[ \left( \begin{matrix} dp[i][1] & dp[i][2] & dp[i][3] & \cdots & dp[i][m] \end{matrix} \right) * A_i= \left( \begin{matrix} dp[i + 1][1] & dp[i + 1][2] & dp[i + 1][3] & \cdots & dp[i + 1][m] \end{matrix} \right) \] 然后用线段树维护矩阵乘积即可 从（1，x）走到（n，y）只需把x位置置为1，然后乘以\(\prod_{i = 1}^n A_i\)代码：
#include#include #include #include #include #include #include #include #include #include #include #define ll long longusing namespace std;const int maxn = 50000 + 5;const int INF = 0x3f3f3f3f;const ll MOD = 1e9 + 7;int n, m, q;int mp[maxn][12];char s[12];struct Mat{ ll s[12][12]; void init_zero(){ for(int i = 0; i < 12; i++) for(int j = 0; j < 12; j++) s[i][j] = 0; }};Mat pmul(Mat a, Mat b, int len){ Mat c; c.init_zero(); for(int i = 1; i <= len; i++){ for(int j = 1; j <= len; j++){ for(int k = 1; k <= len; k++){ c.s[i][j] = (c.s[i][j] + a.s[i][k] * b.s[k][j]) % MOD; } } } return c;}Mat mul[maxn << 2], a[maxn];void pushup(int rt){ mul[rt] = pmul(mul[rt << 1], mul[rt << 1 | 1], m);}void build(int l, int r, int rt){ if(l == r){ for(int i = 1; i <= m; i++) for(int j = 1; j <= m; j++) mul[rt].s[i][j] = a[l].s[i][j]; return; } int m = (l + r) >> 1; build(l, m, rt << 1); build(m + 1, r, rt << 1 | 1); pushup(rt);}void update(int pos, int l, int r, Mat aa, int rt){ if(l == r){ for(int i = 1; i <= m; i++) for(int j = 1; j <= m; j++) mul[rt].s[i][j] = aa.s[i][j]; return; } int m = (l + r) >> 1; if(pos <= m) update(pos, l, m, aa, rt << 1); else update(pos, m + 1, r, aa, rt << 1 | 1); pushup(rt);}int main(){ scanf("%d%d%d", &n, &m, &q); for(int i = 1; i <= n; i++){ scanf("%s", s + 1); for(int j = 1; j <= m; j++){ mp[i][j] = s[j] - '0'; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ int base; base = 1; for(int k = j; k >= 1; k--){ if(mp[i][k] == 1) base = 0; a[i].s[k][j] = base; } base = 1; for(int k = j; k <= m; k++){ if(mp[i][k] == 1) base = 0; a[i].s[k][j] = base; } } }// for(int k = 1; k <= n; k++){// for(int i = 1; i <= m; i++){// for(int j = 1; j <= m; j++){// printf("%d ", a[k].s[i][j]);// }// puts("");// }// puts("*****");// } build(1, n, 1); while(q--){ int ques, i, j; scanf("%d", &ques); scanf("%d%d", &i, &j); if(ques == 1){ mp[i][j] = !mp[i][j]; for(int j = 1; j <= m; j++){ int base; base = 1; for(int k = j; k >= 1; k--){ if(mp[i][k] == 1) base = 0; a[i].s[k][j] = base; } base = 1; for(int k = j; k <= m; k++){ if(mp[i][k] == 1) base = 0; a[i].s[k][j] = base; } } update(i, 1, n, a[i], 1); } else{ Mat ret; ret.init_zero(); ret.s[1][i] = 1; ret = pmul(ret, mul[1], m); printf("%lld\n", ret.s[1][j]); } } return 0;}/*2 6 10 0 0 1 0 01 0 1 0 1 0*/