답안 #8931 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
8931	2014-09-26T09:44:33 Z	ekzm0204	The last wizard (kriii2_T)	C++	4 / 4	976 ms	83416 KB

#include <stdio.h>
#include <memory.h>
typedef long long LL;
const int MAXN = 10001;
/*
const int M = 5;
const int M2 = 32;
*/
const int M = 10;
const int M2 = 1024;

LL T, N, A;
LL P[MAXN];
LL dat[MAXN][M];
LL MOD = 1000000007;
class MV {
public:
	LL d[M2];
};

int bitcnt[M2];
MV I;
LL mult[MAXN][M2];

void init() {
	int w = 0;
	for (int i = 1; i < M2; i+=i) {
		bitcnt[i] = w++;
	}
	for (int i = 0; i < N; i++) {
		mult[i][0] = 1;
		for (int j = 1; j < M2; j++) {
			int l = (j ^ (j - 1))&j;
			mult[i][j] = (mult[i][j^l] * dat[i][bitcnt[l]]) % MOD;
		}
	}
	for (int i = 0; i < M2; i++) {
		for (int j = 0; j < N; j++) {
			I.d[i] = (I.d[i] + P[j] * mult[j][i]) % MOD;
		}
	}
}

MV multTime(MV A, MV B) {
	MV C;
	memset(&C, 0, sizeof(C));
	for (int i = 0; i<M2; i++) {
		for (int j = i;; j = (j - 1)&i) {
			C.d[i] = (C.d[i] + A.d[j] * B.d[i^j]) % MOD;
			if (j == 0) break;
		}
	}
	return C;
}
MV calcTime(LL T) {
	if (T == 1) return I;
	LL t = T / 2;
	MV half = calcTime(t);
	MV R = multTime(half, half);
	if (T % 2 == 1) R = multTime(R, I);

	return R;
}
int main() {
	scanf("%lld %lld %lld", &T, &N, &A);
	P[0] = A;
	for (int j = 0; j<M; j++) dat[0][j] = 0;

	for (int i = 1; i <= N; i++) {
		scanf("%lld", &P[i]);
		P[0] -= P[i];
		for (int j = 0; j<M; j++) {
			scanf("%lld", &dat[i][j]);
		}
	}
	N++;
	init();

	MV R = calcTime(T);
	LL sol = 0;
	for (int i = 0; i < M2; i++) {
		sol = (sol + R.d[i]) % MOD;
	}
	printf("%lld\n", sol);
	return 0;
}

Subtask #1
1.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	81968 KB	Output is correct
2	Correct	0 ms	81968 KB	Output is correct
3	Correct	0 ms	81968 KB	Output is correct
4	Correct	0 ms	81968 KB	Output is correct
5	Correct	4 ms	81968 KB	Output is correct
6	Correct	4 ms	81968 KB	Output is correct
7	Correct	4 ms	81968 KB	Output is correct
8	Correct	4 ms	81972 KB	Output is correct
9	Correct	4 ms	81972 KB	Output is correct
10	Correct	0 ms	81976 KB	Output is correct
11	Correct	4 ms	81972 KB	Output is correct
12	Correct	4 ms	81968 KB	Output is correct
13	Correct	4 ms	81968 KB	Output is correct
14	Correct	4 ms	81968 KB	Output is correct
15	Correct	0 ms	81972 KB	Output is correct
16	Correct	4 ms	82012 KB	Output is correct
17	Correct	4 ms	82008 KB	Output is correct
18	Correct	4 ms	82008 KB	Output is correct
19	Correct	4 ms	82012 KB	Output is correct
20	Correct	0 ms	81968 KB	Output is correct
21	Correct	0 ms	81968 KB	Output is correct
22	Correct	0 ms	81968 KB	Output is correct
23	Correct	0 ms	81968 KB	Output is correct
24	Correct	4 ms	81968 KB	Output is correct
25	Correct	4 ms	81968 KB	Output is correct
26	Correct	4 ms	81968 KB	Output is correct
27	Correct	4 ms	81968 KB	Output is correct
28	Correct	4 ms	81972 KB	Output is correct
29	Correct	4 ms	81976 KB	Output is correct
30	Correct	4 ms	81972 KB	Output is correct
31	Correct	4 ms	81972 KB	Output is correct
32	Correct	0 ms	81968 KB	Output is correct
33	Correct	0 ms	81968 KB	Output is correct
34	Correct	0 ms	81968 KB	Output is correct
35	Correct	0 ms	81968 KB	Output is correct
36	Correct	4 ms	81968 KB	Output is correct
37	Correct	4 ms	81968 KB	Output is correct
38	Correct	4 ms	81968 KB	Output is correct
39	Correct	4 ms	81968 KB	Output is correct
40	Correct	4 ms	81972 KB	Output is correct
41	Correct	0 ms	81968 KB	Output is correct
42	Correct	0 ms	81968 KB	Output is correct
43	Correct	0 ms	81968 KB	Output is correct
44	Correct	0 ms	81968 KB	Output is correct
45	Correct	4 ms	81968 KB	Output is correct
46	Correct	4 ms	81968 KB	Output is correct
47	Correct	4 ms	81968 KB	Output is correct
48	Correct	4 ms	81972 KB	Output is correct
49	Correct	0 ms	81968 KB	Output is correct
50	Correct	0 ms	81968 KB	Output is correct
51	Correct	0 ms	81968 KB	Output is correct
52	Correct	0 ms	81968 KB	Output is correct
53	Correct	4 ms	81968 KB	Output is correct
54	Correct	4 ms	81968 KB	Output is correct
55	Correct	4 ms	81968 KB	Output is correct
56	Correct	0 ms	81968 KB	Output is correct
57	Correct	0 ms	81968 KB	Output is correct
58	Correct	0 ms	81968 KB	Output is correct
59	Correct	0 ms	81968 KB	Output is correct
60	Correct	4 ms	81968 KB	Output is correct
61	Correct	4 ms	81968 KB	Output is correct
62	Correct	4 ms	81968 KB	Output is correct
63	Correct	0 ms	81968 KB	Output is correct
64	Correct	0 ms	81968 KB	Output is correct
65	Correct	0 ms	81968 KB	Output is correct
66	Correct	0 ms	81968 KB	Output is correct
67	Correct	4 ms	81968 KB	Output is correct
68	Correct	4 ms	81968 KB	Output is correct
69	Correct	0 ms	81968 KB	Output is correct
70	Correct	0 ms	81968 KB	Output is correct
71	Correct	0 ms	81968 KB	Output is correct
72	Correct	0 ms	81968 KB	Output is correct
73	Correct	4 ms	81968 KB	Output is correct
74	Correct	4 ms	81968 KB	Output is correct
75	Correct	0 ms	81968 KB	Output is correct
76	Correct	0 ms	81968 KB	Output is correct
77	Correct	0 ms	81968 KB	Output is correct
78	Correct	0 ms	81968 KB	Output is correct
79	Correct	4 ms	81968 KB	Output is correct
80	Correct	4 ms	81968 KB	Output is correct
81	Correct	0 ms	81968 KB	Output is correct
82	Correct	0 ms	81968 KB	Output is correct
83	Correct	0 ms	81968 KB	Output is correct
84	Correct	0 ms	81968 KB	Output is correct
85	Correct	4 ms	81968 KB	Output is correct
86	Correct	0 ms	81968 KB	Output is correct
87	Correct	0 ms	81968 KB	Output is correct
88	Correct	0 ms	81968 KB	Output is correct
89	Correct	0 ms	81968 KB	Output is correct
90	Correct	4 ms	81968 KB	Output is correct
91	Correct	0 ms	81968 KB	Output is correct
92	Correct	0 ms	81968 KB	Output is correct
93	Correct	0 ms	81968 KB	Output is correct
94	Correct	0 ms	81968 KB	Output is correct
95	Correct	4 ms	81968 KB	Output is correct
96	Correct	0 ms	81968 KB	Output is correct
97	Correct	0 ms	81968 KB	Output is correct
98	Correct	0 ms	81968 KB	Output is correct
99	Correct	0 ms	81968 KB	Output is correct
100	Correct	4 ms	81968 KB	Output is correct

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	948 ms	83412 KB	Output is correct
2	Correct	964 ms	83412 KB	Output is correct
3	Correct	936 ms	83336 KB	Output is correct
4	Correct	944 ms	83376 KB	Output is correct
5	Correct	952 ms	83416 KB	Output is correct
6	Correct	944 ms	83176 KB	Output is correct
7	Correct	948 ms	83412 KB	Output is correct
8	Correct	948 ms	83376 KB	Output is correct
9	Correct	952 ms	83416 KB	Output is correct
10	Correct	932 ms	83376 KB	Output is correct
11	Correct	964 ms	83412 KB	Output is correct
12	Correct	928 ms	83292 KB	Output is correct
13	Correct	960 ms	83376 KB	Output is correct
14	Correct	944 ms	83212 KB	Output is correct
15	Correct	964 ms	83412 KB	Output is correct
16	Correct	932 ms	83412 KB	Output is correct
17	Correct	932 ms	83336 KB	Output is correct
18	Correct	940 ms	83376 KB	Output is correct
19	Correct	960 ms	83332 KB	Output is correct
20	Correct	952 ms	83136 KB	Output is correct
21	Correct	968 ms	83376 KB	Output is correct
22	Correct	964 ms	83332 KB	Output is correct
23	Correct	976 ms	83372 KB	Output is correct
24	Correct	960 ms	83416 KB	Output is correct
25	Correct	976 ms	83372 KB	Output is correct
26	Correct	936 ms	83292 KB	Output is correct
27	Correct	940 ms	83296 KB	Output is correct
28	Correct	956 ms	83292 KB	Output is correct
29	Correct	940 ms	83292 KB	Output is correct
30	Correct	948 ms	83292 KB	Output is correct

답안 #8931

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 3.0 / 3.0

Subtask #1
1.0 / 1.0

Subtask #2
3.0 / 3.0