QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#420464 | #8717. 骰子 | ucup-team173 | WA | 1029ms | 8752kb | C++20 | 2.9kb | 2024-05-24 18:50:16 | 2024-05-24 18:50:16 |
Judging History
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'