QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#472749#8238. Dreamy PutatawsyearWA 367ms294472kbC++176.5kb2024-07-11 19:02:102024-07-11 19:02:11

Judging History

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

  • [2024-07-11 19:02:11]
  • 评测
  • 测评结果:WA
  • 用时:367ms
  • 内存:294472kb
  • [2024-07-11 19:02:10]
  • 提交

answer

#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) int((a).size())
#define fi first
#define se second

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T> void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T> void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int mod = 1e9 + 7;
const int maxn = 100010;
const int maxm = 12;
const int maxk = 300;

inline void add(int &x, int y) { x = (x + y >= mod) ? x + y - mod : x + y; }
inline void sub(int &x, int y) { x = (x - y < 0) ? x - y + mod : x - y; }
inline int fpw(int a, int p) { int res = 1; while (p) { if (p & 1) res = 1ll * res * a % mod; p >>= 1, a = 1ll * a * a % mod; } return res; }

int n, m, q, inv, rval[maxn], l[maxn][maxm], r[maxn][maxm], u[maxn][maxm], d[maxn][maxm], e[maxk][maxk];

struct vec {
  int a[maxm];
  vec() { rep (i, 0, 2 * m - 1) a[i] = 0; }
  vec(int x) { rep (i, 0, 2 * m - 1) a[i] = 0; a[0] = x; }
  friend vec operator+(vec x, vec y) {
    rep (i, 0, 2 * m - 1) add(x.a[i], y.a[i]);
    return x;
  }
  friend vec operator-(vec x, vec y) {
    rep (i, 0, 2 * m - 1) sub(x.a[i], y.a[i]);
    return x;
  }
  friend vec operator*(vec x, int y) {
    rep (i, 0, 2 * m - 1) x.a[i] = 1ll * x.a[i] * y % mod;
    return x;
  }
} a[maxn][maxm];

void gauss(int n) {
  rep (i, 1, n) {
    int id = i;
    while (id <= n && !e[id][i]) id++;
    if (id > n) continue;
    rep (j, 1, n + 1) swap(e[i][j], e[id][j]);
    rep (j, 1, n) if (i != j) {
      int coe = 1ll * e[j][i]* fpw(e[i][i], mod - 2) % mod;
      rep (k, 1, n + 1) sub(e[j][k], 1ll * coe * e[i][k] % mod);
    }
  }
}

void check(int x, int tx, int ty) {
  if (x != tx) return;
  a[x][ty] = vec();
}

struct mat {
  int a[maxm][maxm];
  mat() {
    rep (i, 0, 2 * m) rep (j, 0, 2 * m) a[i][j] = 0;
  }
  friend mat operator*(mat x, mat y) {
    mat res;
    rep (i, 0, 2 * m) rep (j, 0, 2 * m) rep (k, 0, 2 * m) add(res.a[i][j], 1ll * x.a[i][k] * y.a[k][j] % mod);
    return res;
  }
} t[maxn << 2], val[maxn];

struct node {
  vec a[maxm];
  node() {
    rep (i, 0, 2 * m) a[i] = vec();
  }
  friend node operator*(node x, mat y) {
    node res;
    rep (i, 0, 2 * m) rep (j, 0, 2 * m) res.a[j] = res.a[j] + x.a[i] * y.a[i][j];
    return res;
  }
};

#define mid ((l + r) >> 1)

void upd(int c, int l, int r, int x, mat v) {
  if (l == r) return t[c] = v, void();
  if (x <= mid) upd(c << 1, l, mid, x, v);
  else upd(c << 1 | 1, mid + 1, r, x, v);
  t[c] = t[c << 1] * t[c << 1 | 1];
}

mat qry(int c, int l, int r, int x, int y) {
  if (l == x && r == y) return t[c];
  if (y <= mid) return qry(c << 1, l, mid, x, y);
  else if (x > mid) return qry(c << 1 | 1, mid + 1, r, x, y);
  else return qry(c << 1, l, mid, x, mid) * qry(c << 1 | 1, mid + 1, r, mid + 1, y);
}

#undef mid

void update(int x) {
  mat e = mat();
  e.a[0][0] = 1;
  rep (i, 1, m) e.a[m + i][i] = 1;
  rep (i, 0, m - 1) {
    add(e.a[m + i + 1][m + i + 1], 1);
    add(e.a[0][m + i + 1], mod - 1);
    add(e.a[m + (i + m - 1) % m + 1][m + i + 1], (mod - l[x][i]) % mod);
    add(e.a[m + (i + 1) % m + 1][m + i + 1], (mod - r[x][i]) % mod);
    add(e.a[i + 1][m + i + 1], (mod - u[x][i]) % mod);
    int inv = fpw(d[x][i], mod - 2);
    rep (j, 0, 2 * m) e.a[j][m + i + 1] = 1ll * e.a[j][m + i + 1] * inv % mod;
  }
  val[x] = e, upd(1, 0, n - 1, x, val[x]);
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> m, inv = fpw(100, mod - 2);
  rep (i, 0, n - 1) rep (j, 0, m - 1) cin >> l[i][j], l[i][j] = 1ll * l[i][j] * inv % mod;
  rep (i, 0, n - 1) rep (j, 0, m - 1) cin >> r[i][j], r[i][j] = 1ll * r[i][j] * inv % mod;
  rep (i, 0, n - 1) rep (j, 0, m - 1) cin >> u[i][j], u[i][j] = 1ll * u[i][j] * inv % mod;
  rep (i, 0, n - 1) rep (j, 0, m - 1) cin >> d[i][j], d[i][j] = 1ll * d[i][j] * inv % mod;
  rep (i, 0, n - 1) update(i);
  cin >> q;
  while (q--) {
    int op; cin >> op;
    if (op == 1) {
      int x, y;
      cin >> x >> y;
      cin >> l[x][y] >> r[x][y] >> u[x][y] >> d[x][y];
      l[x][y] = 1ll * l[x][y] * inv % mod;
      r[x][y] = 1ll * r[x][y] * inv % mod;
      u[x][y] = 1ll * u[x][y] * inv % mod;
      d[x][y] = 1ll * d[x][y] * inv % mod;
      update(x);
    } else {
      int sx, sy, tx, ty;
      cin >> sx >> sy >> tx >> ty;
      rep (i, 0, n - 1) rep (j, 0, m - 1) a[i][j] = vec();
      rep (i, 0, ty - 1) a[tx][i].a[i + 1] = 1;
      rep (i, ty + 1, m - 1) a[tx][i].a[i] = 1;
      rep (i, 0, m - 1) a[(tx + 1) % n][i].a[m + i] = 1;
      int pos = (tx + 1) % n;
      node cur;
      rep (i, 0, m - 1) cur.a[i + 1] = a[tx][i];
      rep (i, 0, m - 1) cur.a[m + i + 1] = a[pos][i];
      cur.a[0] = vec(1);
      int lim = (tx + n - 2) % n;
      mat res;
      if (pos <= lim) {
        res = qry(1, 0, n - 1, pos, lim);
      } else {
        res = qry(1, 0, n - 1, pos, n - 1) * qry(1, 0, n - 1, 0, lim);
      }
      cur = cur * res, pos = (lim + 1) % n;
      rep (i, 1, 2 * m - 1) rep (j, 1, 2 * m) e[i][j] = 0;
      int tot = 0;
      rep (i, 0, m - 1) a[(pos + n - 1) % n][i] = cur.a[i + 1];
      rep (i, 0, m - 1) a[pos][i] = cur.a[m + i + 1];
      rep (i, 0, m - 1) {
        vec cur = a[pos][i];
        cur = cur - a[pos][(i + m - 1) % m] * l[pos][i];
        cur = cur - a[pos][(i + 1) % m] * r[pos][i];
        cur = cur - a[(pos + n - 1) % n][i] * u[pos][i];
        cur = cur - a[(pos + 1) % n][i] * d[pos][i];
        cur = cur - vec(1);
        e[++tot][2 * m] = cur.a[0];
        rep (j, 1, 2 * m - 1) e[tot][j] = cur.a[j];
      }
      pos = (pos + 1) % n;
      rep (i, 0, m - 1) if (i != ty) {
        vec cur = a[pos][i];
        cur = cur - a[pos][(i + m - 1) % m] * l[pos][i];
        cur = cur - a[pos][(i + 1) % m] * r[pos][i];
        cur = cur - a[(pos + n - 1) % n][i] * u[pos][i];
        cur = cur - a[(pos + 1) % n][i] * d[pos][i];
        cur = cur - vec(1);
        e[++tot][2 * m] = cur.a[0];
        rep (j, 1, 2 * m - 1) e[tot][j] = cur.a[j];
      }
      gauss(2 * m - 1);
      rep (i, 1, 2 * m - 1) rval[i] = 1ll * e[i][2 * m] * fpw(e[i][i], mod - 2) % mod;
      rep (i, 1, 2 * m - 1) rval[i] = (mod - rval[i]) % mod;
      int ans = a[sx][sy].a[0];
      rep (i, 1, 2 * m - 1) ans = (ans + 1ll * rval[i] * a[sx][sy].a[i] % mod) % mod;
      cout << ans << '\n';
    }
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 294472kb

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: 115ms
memory: 284976kb

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: 202ms
memory: 285176kb

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: 332ms
memory: 285200kb

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: 128ms
memory: 286828kb

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: 226ms
memory: 285300kb

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: 367ms
memory: 286624kb

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: -100
Wrong Answer
time: 139ms
memory: 286944kb

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:

0
74093968
190343982
0
102755459
671175664
701973110
602834246
516593273
331066997
859528771
0
970030107
394559031
237142618
869135259
0
324920125
954118145
742091927
0
550194093
802575663
95826696
0
36175815
772030766
568903915
0
698003803
839664171
825825913
347368617
339174903
269036861
813528314...

result:

wrong answer 1st numbers differ - expected: '424703237', found: '0'