题意
给一个(n imes m)的01矩阵，1代表有墙，否则没有，每一步可以从(b[i][j])走到(b[i+1][j]),(b[i][j-1]),(b[i][j+1])，有两种询问：
- (q=1),将(b[x][y])的状态反转
- (q=2),计算从(b[1][x])走到(b[n][y])的方案数
分析
先不考虑状态反转的情况，设(dp[i][j])为从第(i-1)层经过(b[i-1][j])到达(b[i][j])的方案数
[dp[i][j]=sum(dp[i-1][k]~for~(k<j~and~b[i-1][k]=b[i-1][k+1]=dots=b[i-1][j]=0))\
+sum(dp[i-1][k]~for~(k>j~and~b[i-1][k]=b[i-1][k-1]=dots=b[i-1][j]=0))
]
(dp[i][j])等于(b[i-1][j])向左和向右(b[i-1][k])都等于0的那些(dp[i-1][k])的和
| 0 | 0 | 0 | 1 | 0 | 0 |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 0 |
例如当n=2,m=6时
(dp[2][2]=dp[1][1]+dp[1][2]+dp[1][3])
(dp[2][6]=dp[1][5]+dp[1][6])
第(i)行的dp值到第(i+1)行的dp值的转移可以用矩阵(Mi)实现
用上图的例子，从第1行转移到第2行
[left [ egin{matrix}dp[1][1]\dp[1][2]\dp[1][3]\dp[1][4]\dp[1][5]\dp[1][6]end{matrix}
ight ] imes
left [ egin{matrix}1&1&1&0&0&0\1&1&1&0&0&0\1&1&1&0&0&0\0&0&0&0&0&0\
0&0&0&0&1&1\0&0&0&0&1&1end{matrix}
ight ]
=left [ egin{matrix}dp[2][1]\dp[2][2]\dp[2][3]\dp[2][4]\dp[2][5]\dp[2][6]end{matrix}
ight ]
]
求从(b[1][x])走到(b[n][y])的方案数，即令(dp[1][x]=1),求(dp[n+1][y])。
若令(ans=M_1 imes M_2 imes M_3 imes dots imes M_n)
则答案为(ans[x][y])
用线段树维护(M_1dots M_n),反转(b[x][y])操作就变成了单点修改，问题就完美解决了
Code
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=5e4+10;
int n,m,q;
char b[maxn][11];
int a[maxn][11];
struct node{
ll a[11][11];
node operator *(const node &r) const{
node res;
memset(res.a,0,sizeof(res.a));
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
for(int k=1;k<=m;k++){
res.a[i][j]=(res.a[i][j]+a[i][k]*r.a[k][j]%mod)%mod;
}
}
}
return res;
}
}tr[maxn<<2];
void pp(int p){
tr[p]=tr[p<<1]*tr[p<<1|1];
}
void cal(int p,int l){
memset(tr[p].a,0,sizeof(tr[p].a));
for(int i=1;i<=m;i++){
int pos=i;
while(pos<=m&&!a[l][pos]){
tr[p].a[i][pos]=1;
pos++;
}
pos=i;
while(pos>=1&&!a[l][pos]){
tr[p].a[i][pos]=1;
pos--;
}
}
}
void bd(int l,int r,int p){
if(l==r){
cal(p,l);
return;
}int mid=l+r>>1;
bd(lson);bd(rson);
pp(p);
}
void up(int x,int l,int r,int p){
if(l==r){
cal(p,l);
return;
}int mid=l+r>>1;
if(x<=mid) up(x,lson);
else up(x,rson);
pp(p);
}
int main(){
//ios::sync_with_stdio(false);
//freopen("in","r",stdin);
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++){
scanf("%s",b[i]+1);
for(int j=1;j<=m;j++){
a[i][j]=(b[i][j]-'0');
}
}
bd(1,n,1);
while(q--){
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if(op==1){
a[x][y]^=1;
up(x,1,n,1);
}else{
printf("%lld
",tr[1].a[x][y]);
}
}
return 0;
}