QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#417010#8717. 骰子ucup_team_qiuly#RE 1ms4208kbC++172.4kb2024-05-22 12:47:452024-05-22 12:47:46

Judging History

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

  • [2024-05-22 12:47:46]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:4208kb
  • [2024-05-22 12:47:45]
  • 提交

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

output:


result: