QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#472779#8238. Dreamy PutatawsyearWA 140ms285032kbC++177.0kb2024-07-11 19:17:202024-07-11 19:17:20

Judging History

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

  • [2024-07-11 19:17:20]
  • 评测
  • 测评结果:WA
  • 用时:140ms
  • 内存:285032kb
  • [2024-07-11 19:17:20]
  • 提交

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;
  }
  void clear() {
    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 (j, 0, m - 1) a[tx][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;
      rep (i, 0, m - 1) cur.a[i + 1] = a[tx][i];
      rep (i, 0, m - 1) cur.a[m + i + 1] = a[(tx + 1) % n][i];
      rep (i, 0, m - 1) a[sx][i] = vec();
      cur.a[0] = vec(1);
      res.clear();
      pos = (tx + 1) % n, lim = (sx + n - 1) % n;
      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;
      rep (i, 0, m - 1) a[sx][i] = cur.a[m + i + 1];
      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: 4ms
memory: 285032kb

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

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
727939389
433211214
322045805
617604648
560168264
819436272
601016121
500019039
543971002
166037359
789868594
190125526
757433456
254373638
982293964
982293964
853196341
504864820
764730651
545590959
586948249
843898620
592509932
508256498
954689273
713397189
518777787
988654370
...

result:

wrong answer 3rd numbers differ - expected: '950211149', found: '727939389'