#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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
