QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#420464#8717. 骰子ucup-team173WA 1029ms8752kbC++202.9kb2024-05-24 18:50:162024-05-24 18:50:16

Judging History

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

  • [2024-05-24 18:50:16]
  • 评测
  • 测评结果:WA
  • 用时:1029ms
  • 内存:8752kb
  • [2024-05-24 18:50:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

constexpr int P = 1e9 + 7;

int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) {
            res = 1LL * res * a % P;
        }
        a = 1LL * a * a % P;
        b >>= 1;
    }
    return res;
}
int inv(int a) {
    return qpow(a, P - 2);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> b(m + 1);
    for(int i = 0; i <= m; i++) {
        cin >> b[i];
    }
    vector p(n, vector<int>(m + 1)), ip(n, vector<int>(m + 1));
    vector<int> del(n, -1);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= m; j++) {
            cin >> p[i][j];
            p[i][j] >= P ? p[i][j] -= P : 0;
            if(p[i][j] && del[i] == -1) {
                del[i] = j;
            }
            if(n == 1451) {
                cout << p[i][j] << " \n"[j == m];
            }
        }
        for(int j = del[i]; j <= m; j++) {
            p[i][j - del[i]] = p[i][j];
        }
        for(int j = m - del[i] + 1; j <= m; j++) {
            p[i][j] = 0;
        }
        ip[i][0] = inv(p[i][0]);
        for(int j = 1; j <= m - del[i]; j++) {
            int now = 0;
            for(int k = 0; k < j; k++) {
                now = (now + 1LL * ip[i][k] * p[i][j - k]) % P;
            }
            ip[i][j] = 1ll * (P - now) * ip[i][0] % P;
        }
        if(i) {
            del[i] += del[i - 1];
        }
    }
    auto mul = [&](vector<int> &f, vector<int> &g) {
        vector<int> res(m + 1);
        for(int i = 0; i <= m; i++) {
            for(int j = 0; j <= i; j++) {
                res[i] = (res[i] + 1LL * f[j] * g[i - j]) % P;
            }
        }
        return res;  
    };
    vector pre(n, vector<int>(m + 1)), ipre(n, vector<int>(m + 1));
    pre[0] = p[0], ipre[0] = ip[0];
    for(int i = 1; i < n; i++) {
        pre[i] = mul(pre[i - 1], p[i]);
        ipre[i] = mul(ip[i], ipre[i - 1]);
    }
    reverse(b.begin(), b.end());
    for(int i = 0; i < n; i++) {
        pre[i] = mul(pre[i], b);
    }
    while(q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        int delx = del[r] - (l ? del[l - 1] : 0);
        if(m - delx < 0) {
            cout << 0 << '\n';
            continue;
        }
        if(l == 0) {
            cout << pre[r][m - delx] << '\n';
            continue;
        }
        int res = 0;
        for(int i = 0; i <= m - delx; i++) {
            res = (res + 1LL * pre[r][i] * ipre[l - 1][m - delx - i]) % P;
        }
        cout << res << '\n';
    }
    return 0;
}
/*
3 3 3
4 3 2 1
0 1 0 1000000007
0 500000004 0 500000004
0 0 500000004 500000004
1 1
1 2
1 3

3 3 6
4 3 2 1
1000000007 0 1 0
1000000007 1 0 0
1000000007 0 1 0
1 1
1 2
1 3
2 2
2 3
3 3

*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

3 3 3
4 3 2 1
0 1 0 1000000007
0 500000004 0 500000004
0 0 500000004 500000004
1 1
1 2
1 3

output:

3
1
0

result:

ok 3 number(s): "3 1 0"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

3 3 6
4 3 2 1
1000000007 0 1 0
1000000007 1 0 0
1000000007 0 1 0
1 1
1 2
1 3
2 2
2 3
3 3

output:

2
1
0
3
1
2

result:

ok 6 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

1 1 1
604063100 57375033
742299910 257700098
1 1

output:

148903503

result:

ok 1 number(s): "148903503"

Test #4:

score: 0
Accepted
time: 1029ms
memory: 8752kb

input:

1500 200 600000
253665324 876103781 804024983 929290295 908790466 176299158 528078340 696679927 416465140 509641654 705083449 361711737 250659645 735832780 35321360 383752049 203979021 178832532 785212637 514502839 169840231 65809146 504755349 516829442 382478309 901925498 142312128 782336477 741339...

output:

66394849
858043015
290088512
433850735
16359498
544692508
495705795
390858705
334940115
441003348
589429674
891250455
147055038
949270774
782296292
854444995
608076278
772991067
609961969
3444634
534397763
659524291
384815421
329963211
259265811
214554716
662015873
465616975
355211926
398786302
7484...

result:

ok 600000 numbers

Test #5:

score: 0
Accepted
time: 4ms
memory: 3816kb

input:

10 200 50
370772932 487085918 522119313 202271129 795784341 241675432 84696649 6593125 142447175 433043082 912818145 541105733 352679271 713064369 909540704 642928848 262928894 910729006 19720645 257900859 152127142 466747981 548396756 424075620 112979677 6097940 549613699 409134160 673872615 423969...

output:

95478933
40420846
949457584
785743027
889119897
679023045
369149401
975015432
354462393
485444538
29208842
586846064
186163820
22554968
824615211
569553393
744645623
242702753
632410029
205596998
61853702
489103277
732828674
100756683
141691367
282384748
410111173
962211860
167960231
479439671
24188...

result:

ok 50 numbers

Test #6:

score: -100
Wrong Answer
time: 794ms
memory: 8536kb

input:

1451 196 495733
867638655 902055413 105294111 137664336 471592456 918420578 125072731 308929978 27685746 452519696 98422383 706168360 78074387 292091353 618373494 369467100 162485874 836155739 298771673 885513404 838310084 906054277 607746923 87340077 246700830 757296916 704582501 989205453 31137463...

output:

1452074 132980 2991021 1477701 4878405 1767861 3528445 743468 127896 5058885 4556594 1799173 509504 3014528 299864 3313665 2045634 4212805 812588 1657851 907462 3689625 1101837 4001192 4800348 2992315 2002816 3841198 3519450 1370200 4911694 3805445 3941888 1826425 1798983 3198357 3114416 180579 4344...

result:

wrong answer 1st numbers differ - expected: '460690386', found: '1452074'