QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#398054 | #8238. Dreamy Putata | ucup-team173 | WA | 209ms | 228828kb | C++20 | 5.7kb | 2024-04-24 21:36:39 | 2024-04-24 21:36:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7, MAXN = 1e5 + 5;
int Fpow(int x, int k) {
int ans = 1;
for(; k; k >>= 1, x = 1ll * x * x % Mod) {
if(k & 1) {
ans = 1ll * ans * x % Mod;
}
}
return ans;
}
int n, m;
vector<vector<int>> l, r, u, d;
struct Mat{
int a[12][12];
Mat() {
memset(a, 0, sizeof(a));
}
int* operator [] (int x) {
return a[x];
}
friend Mat operator*(Mat a, Mat b) {
Mat c;
for(int i = 0; i < ((m + 1) << 1); i++) {
for(int j = 0; j < ((m + 1) << 1); j++) {
for(int k = 0; k < ((m + 1) << 1); k++) {
c[i][j] = (c[i][j] + 1ll * a[i][k] * b[k][j]) % Mod;
}
}
}
return c;
}
};
Mat get(int x) {
Mat c;
for(int i = 0; i < m; i++) {
c[m + i][i] = 1;
}
for(int i = 0; i < m; i++) {
int inv = Fpow(d[x][i], Mod - 2);
c[m + i][m + i] = inv;
c[i][m + i] = Mod - 1ll * u[x][i] * inv % Mod;
c[m + (i ? i - 1 : m - 1)][m + i] = Mod - 1ll * l[x][i] * inv % Mod;
c[m + (i != m - 1 ? i + 1 : 0)][m + i] = Mod - 1ll * r[x][i] * inv % Mod;
c[m << 1 | 1][m + i] = Mod - inv;
}
c[m << 1][m << 1] = 1;
c[m << 1 | 1][m << 1 | 1] = 1;
return c;
}
Mat t[MAXN << 2];
#define ls x << 1
#define rs x << 1 | 1
void pushup(int x) {
t[x] = t[x << 1] * t[x << 1 | 1];
}
void build(int x, int l, int r) {
if(l == r) {
t[x] = get(l);
return ;
}
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
pushup(x);
}
void mdy(int x, int l, int r, int p) {
if(l == r) {
t[x] = get(l);
return ;
}
int mid =(l + r) >> 1;
if(p <= mid) mdy(ls, l, mid, p);
else mdy(rs, mid + 1, r, p);
pushup(x);
}
Mat ask(int x, int l, int r, int ql, int qr) {
if(ql > qr) {
Mat t;
for(int i = 0; i < ((m + 1) << 1); i++) {
t[i][i] = 1;
}
return t;
}
if(ql <= l && r <= qr) {
return t[x];
}
int mid = (l + r) >> 1;
if(qr <= mid) return ask(ls, l, mid, ql, qr);
else if(ql > mid) return ask(rs, mid + 1, r, ql, qr);
else return ask(ls, l, mid, ql, qr) * ask(rs, mid + 1, r, ql, qr);
}
vector<int> calc1(int tx, int ty) {
vector<vector<int>> equ(m << 1 | 1, vector<int>((m + 1) << 1, 0));
Mat res1 = ask(1, 0, n - 1 , 0, tx);
for(int i = 0; i < ((m + 1) << 1); i++) {
equ[0][i] = res1[i][ty];
res1[i][ty + m] = 0;
}
res1[m << 1][ty + m] = 1;
res1[m << 1 | 1][ty + m] = 0;
Mat res2 = ask(1, 0, n - 1, tx + 1, n - 1);
Mat res = res1 * res2;
for(int i = 0; i < (m << 1); i++) {
for(int j = 0; j < ((m + 1) << 1); j++) {
equ[i + 1][j] = res[j][i];
}
equ[i + 1][i] = (equ[i + 1][i] + Mod - 1) % Mod;
}
for(int i = 0; i < (m << 1 | 1); i++) {
if(!equ[i][i]) {
for(int j = i; j < (m << 1 | 1); j++) {
if(equ[j][i]) {
swap(equ[i], equ[j]);
break;
}
}
}
for(int j = i + 1; j < (m << 1 | 1); j++) {
int t = 1ll * equ[j][i] * Fpow(equ[i][i], Mod - 2) % Mod;
for(int k = i; k < ((m + 1) << 1); k++) {
equ[j][k] = (equ[j][k] - 1ll * t * equ[i][k] % Mod + Mod) % Mod;
}
}
}
vector<int> val(m << 1 | 1, 0);
for(int i = (m << 1); i >= 0; i--) {
int res = equ[i][m << 1 | 1];
for(int j = i + 1; j < (m << 1 | 1); j++) {
res = (res + 1ll * val[j] * equ[i][j]) % Mod;
}
val[i] = 1ll * (Mod - res) * Fpow(equ[i][i], Mod - 2) % Mod;
}
return val;
}
int calc2(int sx, int sy, int tx, int ty, const vector<int> &val) {
Mat res;
if(sx <= tx) res = ask(1, 0, n - 1, 0, sx);
else {
Mat res1 = ask(1, 0, n - 1 , 0, tx);
for(int i = 0; i < ((m + 1) << 1); i++) {
res1[i][ty + m] = 0;
}
Mat res2 = ask(1, 0, n - 1, tx + 1, sx);
res = res1 * res2;
}
int ans = 0;
for(int i = 0; i < (m << 1 | 1); i++) {
ans = (ans + 1ll * res[i][sy] * val[i]) % Mod;
}
ans = (ans + res[m << 1 | 1][sy]) % Mod;
return ans;
}
void solve() {
cin >> n >> m;
auto init = [](int n, int m, vector<vector<int>> &a) {
int inv = Fpow(100, Mod - 2);
a.resize(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
a[i][j] = 1ll * a[i][j] * inv % Mod;
}
}
};
init(n, m, l);
init(n, m, r);
init(n, m, u);
init(n, m, d);
build(1, 0, n - 1);
int q;
cin >> q;
for(int i = 1; i <= q; i++) {
int opt;
cin >> opt;
if(opt == 1) {
int x, y, cl, cr, cu, cd;
cin >> x >> y >> cl >> cr >> cu >> cd;
int inv = Fpow(100, Mod - 2);
l[x][y] = 1ll * cl * inv % Mod, r[x][y] = 1ll * cr * inv % Mod;
u[x][y] = 1ll * cu * inv % Mod, d[x][y] = 1ll * cd * inv % Mod;
mdy(1, 0, n - 1, x);
} else {
int sx, sy, tx, ty;
cin >> sx >> sy >> tx >> ty;
vector<int> val = calc1(tx, ty);
cout << calc2(sx, sy, tx, ty, val) << '\n';
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 228564kb
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: 209ms
memory: 228828kb
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:
88164429 275534854 0 433211214 322045805 295825946 0 819436272 601016121 500019039 0 0 576205173 0 757433456 254373638 69617625 69617625 853196341 504864820 764730651 545590959 586948249 843898620 592509932 770682551 954689273 713397189 518777787 988654370 0 0 653575289 628824260 481722188 455588405...
result:
wrong answer 1st numbers differ - expected: '794352047', found: '88164429'