QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#417010 | #8717. 骰子 | ucup_team_qiuly# | RE | 1ms | 4208kb | C++17 | 2.4kb | 2024-05-22 12:47:45 | 2024-05-22 12:47:46 |
Judging History
answer
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) fprintf (stderr, __VA_ARGS__)
#define lep(i, l, r) for (int i = (l), i##_end = (r); i <= i##_end; ++ i)
#define rep(i, r, l) for (int i = (r), i##_end = (l); i >= i##_end; -- i)
char _c; bool _f; template <class T> inline void IN (T & x) {
_f = 0, x = 0; while (_c = getchar (), ! isdigit (_c)) if (_c == '-') _f = 1;
while (isdigit (_c)) x = x * 10 + _c - '0', _c = getchar (); if (_f) x = - x;
}
const int mod = 1e9 + 7;
inline int mul (int x, int y) { return 1ll * x * y % mod; }
inline int qpow (int x, int y, int r = 1) { for ( ; y; y >>= 1, x = mul (x, x)) if (y & 1) r = mul (r, x); return r; }
inline void pls (int & x, int y) { x += y; if (x >= mod) x -= mod; }
inline int add (int x, int y) { x += y; if (x >= mod) x -= mod; return x; }
const int N = 1.5e3 + 5;
const int M = 2e2 + 5;
int n, m, b[M], p[N][M];
vector <vector <int> > pl[N << 2], pr[N << 2];
inline void doit (vector <int> & a, int x) {
vector <int> b (m + 1);
lep (i, 0, m) lep (j, 0, m - i) {
pls (b[i + j], mul ( a[i], p[x][j] ));
}
swap (a, b);
}
void build (int x, int l, int r) {
if (l == r) {
// empty
} else {
int mid = l + r >> 1;
build (x << 1, l, mid);
build (x << 1 | 1, mid + 1, r);
pl[x].resize ( mid - l + 2 );
pl[x][(mid + 1) - l].resize ( m + 1 );
pl[x][(mid + 1) - l][0] = 1;
rep (i, mid, l) {
pl[x][i - l] = pl[x][i + 1 - l];
doit ( pl[x][i - l], i );
}
pr[x].resize ( r - mid + 1 );
pr[x][mid - mid].resize ( m + 1 );
pr[x][mid - mid][0] = 1;
lep (i, mid + 1, r) {
pr[x][i - mid] = pr[x][i - 1 - mid];
doit ( pr[x][i - mid], i );
}
}
}
int query (int x, int l, int r, int L, int R) {
int mid = l + r >> 1;
if (L <= mid + 1 && R >= mid) {
int ret = 0;
lep (i, 0, m) lep (j, 0, m - i) {
int coe = mul (pl[x][L - l][i], pr[x][R - mid][j]);
pls (ret, mul ( coe, b[i + j] ));
}
return ret;
} else {
if (R < mid) {
return query (x << 1, l, mid, L, R);
} else {
return query (x << 1 | 1, mid + 1, r, L, R);
}
}
}
signed main () {
int q;
IN (n), IN (m), IN (q);
lep (i, 0, m) IN (b[i]);
lep (i, 1, n) {
lep (j, 0, m) {
IN (p[i][j]);
}
}
build (1, 1, n);
for (int l, r; q; -- q) {
IN (l), IN (r);
printf ("%d\n", query (1, 1, n, l, r));
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4208kb
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: 4164kb
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: -100
Runtime Error
input:
1 1 1 604063100 57375033 742299910 257700098 1 1