| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1325209 | gs12117 | The last wizard (kriii2_T) | C11 | 0 ms | 0 KiB |
#include<cstdio>
int train, n, base;
const int mod = 1000000007;
long long int multsum[1024];
long long int cmultsum[1024];
long long int b[1024][1024];
long long int c[1024][1024];
long long int d[1024][1024];
int vlist[1024][1024];
int vll[1024];
int minc[12];
long long int mpow(long long int x, int y) {
if (y == 0)return 1;
long long int r = mpow(x, y / 2);
r *= r;
r %= mod;
if (y % 2 == 1) {
r *= x;
r %= mod;
}
return r;
}
void buildc(int y) {
if (y == 1)return;
buildc(y / 2);
for (int i = 0; i < (1 << 10); i++) {
for (int j = 0; j < vll[i]; j++) {
int x = vlist[i][j];
d[i][x] = 0;
for (int k = 0; k < vll[i - x]; k++) {
int y = vlist[i - x][k];
d[i][x] += c[i][x + y] * c[x + y][x];
d[i][x] %= mod;
}
}
}
for (int i = 0; i < (1 << 10); i++) {
for (int j = 0; j < vll[i]; j++) {
int x = vlist[i][j];
c[i][x] = d[i][x];
}
}
if (y % 2 == 1) {
for (int i = 0; i < (1 << 10); i++) {
for (int j = 0; j < vll[i]; j++) {
int x = vlist[i][j];
d[i][x] = 0;
for (int k = 0; k < vll[i - x]; k++) {
int y = vlist[i - x][k];
d[i][x] += c[i][x + y] * b[x + y][x];
d[i][x] %= mod;
}
}
}
for (int i = 0; i < (1 << 10); i++) {
for (int j = 0; j < vll[i]; j++) {
int x = vlist[i][j];
c[i][x] = d[i][x];
}
}
}
}
int main() {
scanf("%d%d%d", &train, &n, &base);
int cbase = base;
for (int i = 0; i < n; i++) {
int p = 0;
scanf("%d", &p);
for (int j = 0; j < 10; j++) {
scanf("%d", &minc[j]);
}
cbase -= p;
cmultsum[0] = 1;
for (int j = 0; j < 10; j++) {
for (int k = 0; k < (1 << j); k++) {
cmultsum[k + (1 << j)] = cmultsum[k] * minc[j] % mod;
}
}
for (int j = 0; j < (1 << 10); j++) {
multsum[j] += cmultsum[j] * p;
multsum[j] %= mod;
}
}
multsum[0] += cbase;
multsum[0] %= mod;
for (int i = 0; i < (1 << 10); i++) {
for (int j = 0; j <= i; j++) {
if ((i & j) != j)continue;
vlist[i][vll[i]] = j;
vll[i]++;
}
}
for (int i = 0; i < (1 << 10); i++) {
for (int j = 0; j < vll[i]; j++) {
int x = vlist[i][j];
b[i][x] = multsum[i - x];
c[i][x] = multsum[i - x];
}
}
buildc(train);
long long int ans = 0;
for (int i = 0; i < (1 << 10); i++) {
ans += c[(1 << 10) - 1][i];
ans %= mod;
}
printf("%lld\n", ans);
return 0;
}