QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#396728 | #8238. Dreamy Putata | qawszx | RE | 170ms | 201840kb | C++14 | 5.9kb | 2024-04-23 08:44:23 | 2024-04-23 08:44:23 |
Judging History
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 ...