QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#396728#8238. Dreamy PutataqawszxRE 170ms201840kbC++145.9kb2024-04-23 08:44:232024-04-23 08:44:23

Judging History

你现在查看的是最新测评结果

  • [2024-04-23 08:44:23]
  • 评测
  • 测评结果:RE
  • 用时:170ms
  • 内存:201840kb
  • [2024-04-23 08:44:23]
  • 提交

answer

#include <bits/stdc++.h>
#define add(x, y) x = (x + y) % Mo
int scan() {
  int x = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar());
  for (; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0';
  return x;
}
int top, stk[11];
void print(int x) {
  do stk[++top] = x % 10, x /= 10; while (x);
  while (top) putchar('0' + stk[top--]);
}
const int N = 1e5, M = 5, Mo = 1e9 + 7;
int Pow(int x, int y) {
  int res = 1;
  for (; y; y >>= 1) {
    if (y & 1) res = 1ll * res * x % Mo;
    x = 1ll * x * x % Mo;
  }
  return res;
}
const int inv100 = Pow(100, Mo - 2);
int pScan() { return 1ll * scan() * inv100 % Mo; }
int n, m, Q, mat_n, pL[N][M], pR[N][M], pU[N][M], pD[N][M];
struct Matrix {
  int a[11][11];
  Matrix() { memset(a, 0, sizeof a); }
  Matrix(int i, bool right) {
    memset(a, 0, sizeof a);
    if (right)
      for (int j = 0; j < m; ++j) {
        a[m + j][j] = 1;
        int inv = Pow(pD[i][j], Mo - 2);
        a[m + j][m + j] = inv,
        a[j][m + j] = -1ll * pU[i][j] * inv % Mo,
        a[m + (j + 1) % m][m + j] = -1ll * pR[i][j] * inv % Mo,
        a[m + (j - 1 + m) % m][m + j] = -1ll * pL[i][j] * inv % Mo,
        a[2 * m][m + j] = -inv;
      }
    else
      for (int j = 0; j < m; ++j) {
        a[j][m + j] = 1;
        int inv = Pow(pU[i][j], Mo - 2);
        a[j][j] = inv,
        a[m + j][j] = -1ll * pD[i][j] * inv % Mo,
        a[(j + 1) % m][j] = -1ll * pR[i][j] * inv % Mo,
        a[(j - 1 + m) % m][j] = -1ll * pL[i][j] * inv % Mo,
        a[2 * m][j] = -inv;
      }
    a[2 * m][2 * m] = 1;
  }
  inline Matrix operator * (const Matrix &B) const {
    Matrix C;
    for (int i = 0; i < mat_n; ++i) for (int k = 0; k < mat_n; ++k)
      for (int j = 0; j < mat_n; ++j) if (a[i][k] && B.a[k][j])
        add(C.a[i][j], 1ll * a[i][k] * B.a[k][j]);
    return C;
  }
} Unit;
struct Node { int l, r; Matrix matR, matL; } t[2 * N];
#define lc(p) (p << 1)
#define rc(p) (p << 1 | 1)
void pushup(int p) {
  t[p].matR = t[lc(p)].matR * t[rc(p)].matR,
  t[p].matL = t[rc(p)].matL * t[lc(p)].matL;
}
void build(int p, int l, int r) {
  t[p].l = l, t[p].r = r;
  if (l == r) {
    t[p].matR = Matrix(l, true), t[p].matL = Matrix(l, false); return;
  }
  int mid = (l + r) >> 1;
  build(lc(p), l, mid), build(rc(p), mid + 1, r);
  pushup(p);
}
void modify(int p, int x) {
  if (t[p].l == t[p].r) {
    t[p].matR = Matrix(x, true), t[p].matL = Matrix(x, false); return;
  }
  modify(x <= t[lc(p)].r ? lc(p) : rc(p), x);
  pushup(p);
}
Matrix queryR(int p, int l, int r) {
  if (l <= t[p].l && t[p].r <= r) return t[p].matR;
  if (r <= t[lc(p)].r) return queryR(lc(p), l, r);
  if (t[rc(p)].l <= l) return queryR(rc(p), l, r);
  return queryR(lc(p), l, r) * queryR(rc(p), l, r);
}
Matrix queryL(int p, int l, int r) {
  if (l <= t[p].l && t[p].r <= r) return t[p].matL;
  if (r <= t[lc(p)].r) return queryL(lc(p), l, r);
  if (t[rc(p)].l <= l) return queryL(rc(p), l, r);
  return queryL(rc(p), l, r) * queryL(lc(p), l, r);
}
int a[10][10], b[11];
void Guass() {
  for (int i = 0; i < 2 * m; ++i) {
    for (int j = i; j < 2 * m; ++j)
      if (a[j][i]) { std::swap(a[i], a[j]), std::swap(b[i], b[j]); break; }
    assert(a[i][i]);
    int inv = Pow(a[i][i], Mo - 2); b[i] = 1ll * b[i] * inv % Mo;
    for (int k = 0; k < 2 * m; ++k) a[i][k] = 1ll * a[i][k] * inv % Mo;
    for (int j = 0; j < 2 * m; ++j) if (j != i && a[j][i]) {
      long long base = -a[j][i];
      for (int k = 0; k < 2 * m; ++k) add(a[j][k], base * a[i][k]);
      add(b[j], base * b[i]);
    }
  }
}
int main() {
  n = scan(), m = scan(), mat_n = 2 * m + 1;
  for (int i = 0; i < mat_n; ++i) Unit.a[i][i] = 1;
  for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) pL[i][j] = pScan();
  for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) pR[i][j] = pScan();
  for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) pU[i][j] = pScan();
  for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) pD[i][j] = pScan();
  build(1, 0, n - 1);
  Q = scan();
  while (Q--) {
    int op = scan();
    if (op == 1) {
      int x = scan(), y = scan();
      pL[x][y] = pScan(), pR[x][y] = pScan(), pU[x][y] = pScan(), pD[x][y] = pScan();
      modify(1, x);
    } else {
      int sx = scan(), sy = scan(), tx = scan(), ty = scan();
      Matrix A = tx         ? queryR(1, 0, tx - 1)     : Unit,
             B = tx + 1 < n ? queryL(1, tx + 1, n - 1) : Unit;
      memset(a, 0, sizeof a), memset(b, 0, sizeof b), b[2 * m] = 1;
      for (int j = 0; j < m; ++j) {
        for (int k = 0; k < 2 * m; ++k) a[j][k] = (A.a[k][m + j] - B.a[k][j]) % Mo;
        b[j] = (B.a[2 * m][j] - A.a[2 * m][m + j]) % Mo;
        if (j == ty) {
          for (int k = 0; k < 2 * m; ++k) a[m + j][k] = A.a[k][m + j];
          b[m + j] = -A.a[2 * m][m + j];
        } else {
          for (int k = 0; k < 2 * m; ++k)
            a[m + j][k] = (- A.a[k][m + j]
                           + 1ll * pD[tx][j] * B.a[k][m + j]
                           + 1ll * pU[tx][j] * A.a[k][j]
                           + 1ll * pR[tx][j] * A.a[k][m + (j + 1) % m]
                           + 1ll * pL[tx][j] * A.a[k][m + (j - 1 + m) % m]
                          ) % Mo;
          b[m + j] = (  A.a[2 * m][m + j] - 1
                      - 1ll * pD[tx][j] * B.a[2 * m][m + j]
                      - 1ll * pU[tx][j] * A.a[2 * m][j]
                      - 1ll * pR[tx][j] * A.a[2 * m][m + (j + 1) % m]
                      - 1ll * pL[tx][j] * A.a[2 * m][m + (j - 1 + m) % m]
                     ) % Mo;
        }
      }
      Guass(); int ans = 0;
      if (sx < tx) {
        A = sx         ? queryR(1, 0, sx - 1)     : Unit;
        for (int k = 0; k < mat_n; ++k) add(ans, 1ll * A.a[k][m + sy] * b[k]);
      } else {
        B = sx + 1 < n ? queryL(1, sx + 1, n - 1) : Unit;
        for (int k = 0; k < mat_n; ++k) add(ans, 1ll * B.a[k][sy]     * b[k]);
      }
      print((ans + Mo) % Mo), putchar('\n');
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 195656kb

input:

4 3
1 2 3
4 5 6
7 8 9
10 11 12
23 24 25
26 27 28
29 30 31
32 33 34
10 11 12
13 14 15
16 17 18
19 20 21
66 63 60
57 54 51
48 45 42
39 36 33
4
2 0 1 1 1
2 0 0 3 2
1 1 1 25 25 25 25
2 0 0 3 2

output:

76426175
344136684
555192113

result:

ok 3 number(s): "76426175 344136684 555192113"

Test #2:

score: 0
Accepted
time: 67ms
memory: 195220kb

input:

3 3
95 62 24
70 74 23
53 63 36
2 25 20
13 2 4
16 22 40
2 2 14
11 1 67
17 6 20
1 11 42
6 23 6
14 9 4
30000
2 2 2 0 2
2 2 0 0 0
2 1 0 0 0
1 0 1 28 36 4 32
1 1 1 55 32 12 1
2 2 1 1 0
2 1 2 0 0
1 0 2 89 2 3 6
1 2 0 53 29 8 10
2 2 2 0 1
2 2 0 1 0
1 2 1 83 15 1 1
2 2 1 1 2
1 2 2 54 41 2 3
2 2 0 1 2
1 0 1 ...

output:

794352047
445720561
950211149
433211214
322045805
617604648
966924565
819436272
601016121
500019039
427833008
54797408
789868594
569035765
757433456
254373638
982293964
982293964
853196341
504864820
764730651
545590959
586948249
843898620
592509932
508256498
954689273
713397189
518777787
988654370
9...

result:

ok 15144 numbers

Test #3:

score: 0
Accepted
time: 96ms
memory: 195640kb

input:

3 4
71 12 51 12
85 83 41 85
20 19 3 75
25 25 1 60
12 7 11 10
72 65 13 1
1 44 16 5
1 1 32 3
3 14 69 5
3 19 32 23
2 9 16 2
5 2 15 19
30000
2 2 3 1 3
2 2 0 0 2
2 1 1 0 1
1 2 1 64 29 1 6
1 2 3 20 70 2 8
2 1 3 0 3
1 1 1 87 7 5 1
2 2 1 0 0
2 2 1 0 3
2 2 1 0 1
1 2 3 64 25 4 7
2 2 2 1 3
2 2 0 1 0
2 2 2 1 1
...

output:

354672429
912592651
205898503
454595712
326527558
244765319
546555335
503022787
150107622
215140594
135585822
236524624
320026574
56673681
280529820
593236671
485177445
743045702
401830954
263027327
262401428
875715418
150860374
179088742
530926216
923964115
667195812
555355389
571319510
737826815
2...

result:

ok 15095 numbers

Test #4:

score: 0
Accepted
time: 125ms
memory: 195860kb

input:

3 5
30 59 44 6 16
12 30 11 83 86
58 49 65 50 44
68 24 2 31 34
24 11 74 12 3
32 23 4 2 17
1 15 29 59 5
19 31 6 4 6
6 15 8 5 34
1 2 25 4 45
45 28 9 1 5
4 13 23 43 5
30000
2 2 0 0 3
2 1 2 0 2
1 1 4 75 7 5 13
2 1 3 0 3
2 1 2 0 4
1 0 1 29 4 53 14
1 0 4 88 10 1 1
2 2 4 1 3
2 2 4 1 3
1 1 2 79 14 3 4
2 2 4 ...

output:

518130880
192901969
549392638
587807011
692872396
692872396
17980668
639677814
546570041
285563686
899784603
294224899
300472120
850053405
384430261
300472120
427268842
269195383
688402844
326045142
856426869
371304714
239555499
858574611
249782581
367550595
813603991
235110041
400091873
781877964
3...

result:

ok 15101 numbers

Test #5:

score: 0
Accepted
time: 70ms
memory: 196188kb

input:

4 3
88 61 8
25 67 82
16 72 5
71 24 3
4 31 51
66 17 4
31 26 63
1 8 11
5 7 21
4 4 6
11 1 31
15 11 50
3 1 20
5 12 8
42 1 1
13 57 36
30000
2 2 1 1 0
1 0 1 15 57 26 2
2 2 1 1 2
2 2 2 0 2
2 2 0 0 0
1 0 1 54 22 8 16
1 2 2 75 12 5 8
1 2 2 67 4 11 18
2 3 2 1 2
2 1 1 0 0
1 0 0 10 70 2 18
1 2 1 35 45 1 19
2 1 ...

output:

932295932
233938741
962914267
815912722
593921746
511030278
628154532
228176878
914256121
677597027
882198995
674345936
857722782
760168451
592843949
808131481
511414300
772346610
433759393
630381295
280392804
171039969
661778948
70945073
35883397
783291216
850970394
64550544
976645462
954726136
157...

result:

ok 15053 numbers

Test #6:

score: 0
Accepted
time: 107ms
memory: 196132kb

input:

4 4
64 11 70 2
77 89 4 59
6 25 27 5
63 4 18 2
2 50 16 37
21 5 64 27
80 35 52 91
32 84 58 39
9 31 4 21
1 5 19 6
12 6 17 3
4 7 7 48
25 8 10 40
1 1 13 8
2 34 4 1
1 5 17 11
30000
2 3 3 0 2
2 3 3 2 0
2 1 0 0 2
2 2 2 0 3
2 3 2 0 0
1 1 0 23 67 3 7
1 1 2 35 55 4 6
2 3 3 2 0
1 3 0 43 45 2 10
2 2 2 1 2
1 2 1 ...

output:

334801426
881562250
651785364
269029145
797504056
802317525
440410805
53552375
677589332
658093753
982712164
788895880
961111614
469915277
451427917
456274210
40639936
749247016
771008350
950381441
457182636
209481283
480115371
761237802
49182981
367217021
640094262
160525935
294564634
429528898
122...

result:

ok 15241 numbers

Test #7:

score: 0
Accepted
time: 169ms
memory: 200116kb

input:

4 5
23 58 1 58 70
53 28 81 87 92
30 77 67 56 70
88 69 21 93 36
70 2 67 16 18
3 61 17 2 6
55 5 10 39 14
9 1 16 3 35
3 13 23 7 7
11 5 1 5 1
8 15 1 4 13
2 20 60 3 26
4 27 9 19 5
33 6 1 6 1
7 3 22 1 3
1 10 3 1 3
30000
2 2 3 0 4
2 3 4 2 1
1 1 4 67 20 7 6
2 1 4 0 0
2 3 2 0 4
2 2 0 1 0
1 1 0 70 17 2 11
2 1...

output:

773395519
202993618
363831331
26600683
628490409
965293227
988464346
254121301
37657552
240517728
959914287
429450563
627759885
77881676
628640396
532755563
789153435
734943549
768356171
155599128
586898868
974688108
332913835
782091995
938757871
25868446
879373433
781809249
970823879
749935361
7024...

result:

ok 15156 numbers

Test #8:

score: 0
Accepted
time: 87ms
memory: 201840kb

input:

5 3
45 41 80
78 24 25
14 64 88
77 13 48
78 19 44
38 13 9
12 57 47
20 8 5
19 15 8
9 26 1
7 5 4
7 4 26
59 8 2
2 3 43
2 36 44
10 41 7
3 15 2
7 20 5
2 69 1
11 19 11
30000
2 4 2 2 1
1 3 0 79 7 4 10
1 3 1 25 28 42 5
1 4 1 66 19 12 3
2 4 2 0 1
2 4 2 3 0
1 4 2 81 2 2 15
2 2 2 0 0
2 4 0 0 1
1 0 1 92 5 1 2
2 ...

output:

424703237
74093968
190343982
962559774
102755459
671175664
701973110
602834246
516593273
331066997
859528771
49139165
970030107
394559031
237142618
869135259
952444644
324920125
954118145
742091927
407449341
550194093
802575663
95826696
690734073
36175815
772030766
568903915
533320284
698003803
8396...

result:

ok 15052 numbers

Test #9:

score: 0
Accepted
time: 124ms
memory: 201432kb

input:

5 4
57 88 72 54
52 68 2 33
72 47 16 85
48 71 26 31
13 24 1 36
21 8 11 31
5 1 87 27
7 47 61 7
20 9 59 19
24 36 92 49
8 1 10 11
34 20 5 9
8 2 2 1
21 13 2 27
56 11 1 9
14 3 7 4
9 11 6 31
13 4 21 7
11 7 13 23
7 29 6 6
30000
2 4 0 0 1
2 4 1 3 0
2 4 3 3 0
1 0 1 10 50 15 25
2 3 0 2 3
2 4 1 3 0
2 4 2 2 3
2 ...

output:

50910996
216377646
573900831
94488786
398129185
72553576
227714101
439263073
864769360
737633649
315953214
971053832
297538736
612444954
155336683
149698059
307519489
277288455
434987247
690011402
580947251
261583247
24280548
473637822
957506150
659358847
304584321
805231430
355763909
371671194
3563...

result:

ok 15229 numbers

Test #10:

score: 0
Accepted
time: 170ms
memory: 200184kb

input:

5 5
16 38 3 13 63
94 53 55 11 36
89 60 70 27 78
36 15 75 89 65
69 44 67 66 92
4 3 48 80 31
1 40 31 72 13
7 15 14 17 19
19 50 9 6 4
27 21 24 26 3
9 13 36 2 2
4 4 11 7 44
3 13 13 51 2
30 9 2 1 1
2 8 5 5 4
71 46 13 5 4
1 3 3 10 7
1 12 3 5 1
15 26 14 4 30
2 27 4 3 1
30000
2 3 3 0 4
2 3 3 2 2
1 0 0 34 34...

output:

157640412
687387050
837923934
844421869
274018362
895430369
443299523
382623443
850399991
931489969
759234940
192352559
611861383
387013782
842447071
496743050
623398591
561396284
479647208
336852340
777717261
191482727
633322383
287868764
74768141
632861696
784428747
218665333
627277702
333573501
8...

result:

ok 15144 numbers

Test #11:

score: 0
Accepted
time: 55ms
memory: 200136kb

input:

10 3
81 66 37
60 28 14
78 86 86
48 85 80
35 38 80
6 24 92
42 39 22
51 19 17
24 90 75
84 97 58
8 6 58
15 52 16
4 10 8
30 7 3
51 30 15
62 4 5
50 18 11
38 39 50
72 8 17
10 1 40
2 10 1
16 6 13
14 1 1
21 1 7
2 25 3
26 20 2
4 13 7
7 41 1
1 1 7
4 1 1
9 18 4
9 14 57
4 3 5
1 7 10
12 7 2
6 52 1
4 30 60
4 1 32...

output:

228427104
803896245
264833563
753064087
301119297
725047338
241342719
686145017
602098062
293499112
249785324
771050358
774679486
964267877
470137845
52315848
785143210
282403387
517877956
785226997
445689512
232849844
615681766
129948283
123199230
605814309
15398995
490612360
46486523
376156864
929...

result:

ok 6539 numbers

Test #12:

score: 0
Accepted
time: 66ms
memory: 200968kb

input:

15 4
19 30 58 23
95 35 56 12
73 23 82 3
24 36 64 33
35 83 67 28
79 1 36 24
45 83 39 70
49 21 10 16
11 8 66 75
86 89 44 82
33 84 74 46
91 63 8 4
68 41 30 94
37 29 26 41
73 5 55 14
66 42 25 21
1 7 19 17
16 43 2 69
26 39 10 48
31 14 10 65
5 75 17 43
45 13 25 22
40 66 55 34
44 73 11 17
8 7 26 13
61 5 5 ...

output:

817241723
982734749
482199175
119378443
893638291
979342465
264556338
92052934
958824466
851266810
683720751
872806324
787928882
851735609
807816096
141792886
967921253
692672934
559586634
163827114
976156746
592647529
549317880
658406488
218852213
808431177
539401099
850609482
1883073
656868643
114...

result:

ok 6484 numbers

Test #13:

score: 0
Accepted
time: 123ms
memory: 200892kb

input:

20 5
74 46 89 8 37
52 88 26 44 20
60 50 15 11 39
60 42 90 42 17
54 79 34 49 25
47 34 97 67 66
33 32 57 63 57
54 32 95 41 77
20 30 10 61 75
43 68 59 81 66
50 40 42 26 28
7 72 31 77 76
81 92 31 27 7
10 67 68 71 52
58 42 12 69 35
73 88 66 38 47
71 23 56 66 2
27 49 57 59 90
41 58 71 75 91
8 67 52 65 26
...

output:

639778417
364226267
647053368
883426672
42223536
418385936
943273737
122622223
109902690
422993489
189755364
885103191
233768416
16323535
133413893
368728303
429746539
146564917
232762353
447281254
52315190
375639139
419899498
635167879
757822657
952255724
152964536
238218545
147952347
886296437
428...

result:

ok 6491 numbers

Test #14:

score: -100
Runtime Error

input:

100000 3
1 73 64
52 63 95
30 77 54
84 82 88
42 49 85
50 78 67
58 19 58
35 18 15
5 7 1
1 36 93
68 26 2
86 92 53
81 60 61
16 64 23
85 48 19
36 93 13
69 28 55
64 12 55
5 17 48
96 39 96
36 70 90
38 96 5
2 16 89
20 60 23
77 95 60
26 31 9
44 11 49
96 9 26
58 53 55
2 6 15
6 36 28
69 87 57
37 24 9
75 40 75
...

output:


result: