QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #641032 | #8717. 骰子 | neetman | RE | 1ms | 7756kb | C++17 | 2.2kb | 2024-10-14 17:56:26 | 2024-10-14 17:56:26 |
Judging History
answer
#include<iostream>
#include<cstdio>
using namespace std;
using ll = long long;
const int N = 1500 + 5, M = 205, mod = 1e9 + 7;
int n, m, q;
ll ans[N][N], p[N][M], w[M], f[M][M][M], pre[N][M];
void solve(int l, int r){
if(l == r){
for(int k = 0; k <= m; k ++){
ans[l][r] = (ans[l][r] + w[k] * p[l][k] % mod) % mod;
}
return;
}
int mid = (l + r) / 2;
solve(l, mid); solve(mid + 1, r);
for(int k = 0; k <= m; k ++){
pre[mid][k] = p[mid][k];
pre[mid + 1][k] = p[mid + 1][k];
}
for(int i = mid - 1; i >= l; i --){
for(int j = 0; j <= m; j ++)
pre[i][j] = 0;
for(int j = 0; j <= m; j ++)
for(int k = 0; k + j <= m; k ++)
pre[i][j + k] = (pre[i][j + k] + pre[i + 1][k] * p[i][j] % mod) % mod;
}
for(int i = mid + 2; i <= r; i ++){
for(int j = 0; j <= m; j ++)
pre[i][j] = 0;
for(int j = 0; j <= m; j ++)
for(int k = 0; k + j <= m; k ++)
pre[i][j + k] = (pre[i][j + k] + pre[i - 1][k] * p[i][j] % mod) % mod;
}
for(int i = mid + 1; i <= r; i ++){
for(int j = 0; j <= m; j ++)
for(int k = 0; k + j <= m; k ++)
f[i][j][k] = pre[i][k] * w[j + k] % mod;
for(int j = 0; j <= m; j ++)
for(int k = 1; k + j <= m; k ++)
f[i][j][k] = (f[i][j][k] + f[i][j][k-1]) % mod;
}
for(int i = mid; i >= l; i --)
for(int j = mid + 1; j <= r; j ++)
for(int k = 0; k <= m; k ++)
ans[i][j] = (ans[i][j] + pre[i][k] * f[j][k][m-k] % mod) % mod;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> n >> m >> q;
for(int i = 0; i <= m; i ++)
cin >> w[i];
for(int i = 1; i <= n; i ++){
for(int j = 0; j <= m; j ++){
cin >> p[i][j];
}
}
solve(1, n);
while(q --){
int l, r;
cin >> l >> r;
cout << ans[l][r] << '\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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7752kb
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: 7756kb
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: 5668kb
input:
1 1 1 604063100 57375033 742299910 257700098 1 1
output:
148903503
result:
ok 1 number(s): "148903503"
Test #4:
score: -100
Runtime Error
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...