QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#472749 | #8238. Dreamy Putata | wsyear | WA | 367ms | 294472kb | C++17 | 6.5kb | 2024-07-11 19:02:10 | 2024-07-11 19:02:11 |
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;
}
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'