QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398054#8238. Dreamy Putataucup-team173WA 209ms228828kbC++205.7kb2024-04-24 21:36:392024-04-24 21:36:39

Judging History

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

  • [2024-04-24 21:36:39]
  • 评测
  • 测评结果:WA
  • 用时:209ms
  • 内存:228828kb
  • [2024-04-24 21:36:39]
  • 提交

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;
}

详细

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'