//scnucjh #include <iostream> #include <map> #include <cstdio> #include <algorithm> #include <set> #include <cstring> #include <queue> #include <vector> using namespace std; typedef long long ll; const int maxn = 5e4+5,M=1e9+7; int n,q,m; int a[maxn][10]; struct mat { int a[10][10]; }; void mul(mat &c,const mat &a,const mat &b) { for(int i=0;i<m;i++) for(int j=0;j<m;j++) c.a[i][j]=0; for(int i=0;i<m;i++) { for(int k=0;k<m;k++) { for(int j=0;j<m;j++) { c.a[i][j] = (c.a[i][j]+1ll*a.a[i][k]*b.a[k][j]) % M; } } } } void get(mat &c,int k) { for(int i=0;i<m;i++) for(int j=0;j<m;j++) c.a[i][j]=0; for (int i=0; i<m; i++) { if(a[k][i]) continue; for(int j=i;j>=0 && a[k][j]==0;j--) c.a[i][j]=1; for(int j=i+1;j<m && a[k][j]==0;j++) c.a[i][j]=1; } } #define lc (o<<1) #define rc (lc|1) mat b[1<<17]; struct tree { int n,y; void build(int o,int L,int R) { if(L==R) { get(b[o],L); return; } int M=L+(R-L)/2; build(lc, L, M); build(rc, M+1, R); mul(b[o],b[lc],b[rc]); } void update(int o,int L,int R) { if(L==R) { get(b[o],L); return; } int M=(L+(R-L))/2; if(y<=M) update(lc, L, M); else update(rc, M+1, R); mul(b[o],b[lc],b[rc]); } }t; #undef lc #undef rc int main() { #ifndef ONLINE_JUDGE freopen("data.txt", "r", stdin); #endif int op,x,y; scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;i++) for(int j=0;j<m;j++) scanf("%1d",&a[i][j]); t.build(1, 1, n); while (q--) { scanf("%d%d%d",&op,&x,&y); y--; if(op==1) { a[x][y]^=1; t.y = x; t.update(1, 1, n); }else { printf("%d\n",b[1].a[x-1][y]); } } return 0; }
全部评论
(0) 回帖