1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
using namespace std;
int n, m, q;
const int mod = 1e9 + 7;
const int maxn = 5e4 + 233;
int c[maxn][14];
struct {
int m[14][14];
Martix(){
memset(m, 0, sizeof(m));
}
}mat[maxn << 2], base;
void print(int o){
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
printf("%d%c", mat[o].m[i][j], (j == m ? 'n' : ' '));
}
}
}
Martix operator*(const Martix &a, const Martix &b){
Martix c;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
for(int k = 1; k <= m; k++){
c.m[i][j] = (c.m[i][j] + 1ll * a.m[i][k] * b.m[k][j]) % mod;
}
}
}
return c;
}
void pushup(int o){
mat[o] = mat[o << 1 | 1] * mat[o << 1];
}
void work(int o, int l){
for(int i = 1; i <= m; i++){
int pl, pr;
for(pl = i; pl; pl--){
if(c[l][pl] == 1) break;
}
for(pr = i; pr <= m; pr++){
if(c[l][pr] == 1) break;
}
memset(mat[o].m[i], 0, sizeof(mat[o].m[i]));
for(int j = pl + 1; j <= pr - 1; j++){
mat[o].m[i][j] = 1;
}
}
}
void build(int o, int l, int r){
if(l == r){
work(o, l);
return;
}
int mid = l + r >> 1;
build(o << 1, l, mid);
build(o << 1 | 1, mid + 1, r);
pushup(o);
}
void update(int o, int tl, int tr, int pos){
if(tr < pos || pos < tl) return;
if(pos == tr && pos == tl){
work(o, tl);
return;
}
int mid = tl + tr >> 1;
update(o << 1, tl, mid, pos);
update(o << 1 | 1, mid + 1, tr, pos);
pushup(o);
}
Martix query(int o, int tl, int tr, int l, int r){
if(tr < l || r < tl) return base;
if(l <= tl && tr <= r) return mat[o];
int mid = tl + tr >> 1;
return query(o << 1 | 1, mid + 1, tr, l, r) * query(o << 1, tl, mid, l, r) ;
}
int main(){
scanf("%d %d %d", &n, &m, &q);
for(int i = 1; i <= m; i++)base.m[i][i] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%1d", &c[i][j]);
}
}
build(1, 1, n);
while(q--){
int op, x, y;
scanf("%d %d %d", &op, &x, &y);
if(op == 2){
Martix res;
res.m[x][1] = 1;
res = query(1, 1, n, 1, n) * res;
printf("%dn", res.m[y][1]);
}
else{
c[x][y] ^= 1;
update(1, 1, n, x);
}
}
return 0;
}
|
近期评论