QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#472779 | #8238. Dreamy Putata | wsyear | WA | 140ms | 285032kb | C++17 | 7.0kb | 2024-07-11 19:17:20 | 2024-07-11 19:17:20 |
Judging History
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'