# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
479422 | rainboy | Mobitel (COCI19_mobitel) | C11 | 294 ms | 65540 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#define N 300
#define M 300
#define B 1000
#define MD 1000000007
int vv[N + M], ff[N + M], gg[N + M];
void init() {
int i;
ff[0] = gg[0] = 1;
for (i = 1; i < N + M; i++) {
vv[i] = i == 1 ? 1 : (long long) vv[i - MD % i] * (MD / i + 1) % MD;
ff[i] = (long long) ff[i - 1] * i % MD;
gg[i] = (long long) gg[i - 1] * vv[i] % MD;
}
}
int choose(int n, int k) {
return (long long) ff[n] * gg[k] % MD * gg[n - k] % MD;
}
int main() {
static int aa[N][M], dp[N][M][B], dq[M][B];
int n, m, c, i, j, a, b, b1, b2, x, ans;
init();
scanf("%d%d%d", &n, &m, &c);
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
scanf("%d", &aa[i][j]);
if (c == 1)
ans = 0;
else {
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if (i == 0 && j == 0)
dp[i][j][1] = 1;
else
for (b = B - 1; b >= 1; b--) {
dp[i][j][b] = 0;
if (i > 0 && b % (a = aa[i - 1][j]) == 0)
dp[i][j][b] = (dp[i][j][b] + dp[i - 1][j][b / a]) % MD;
if (j > 0 && b % (a = aa[i][j - 1]) == 0)
dp[i][j][b] = (dp[i][j][b] + dp[i][j - 1][b / a]) % MD;
}
a = aa[n - 1][m - 1];
ans = 0;
for (b = 0; b * a < c && b * a < B; b++)
ans = (ans + dp[n - 1][m - 1][b]) % MD;
for (i = n - 1; i >= 0; i--) {
for (j = m - 1; j >= 0; j--)
if (i == n - 1 && j == m - 1)
dq[j][1] = 1;
else
for (b = B - 1; b >= 1; b--) {
int x = dq[j][b];
dq[j][b] = 0;
if (i + 1 < n && b % (a = aa[i + 1][j]) == 0)
dq[j][b] = (dq[j][b] + (a == 1 ? x : dq[j][b / a])) % MD;
if (j + 1 < m && b % (a = aa[i][j + 1]) == 0)
dq[j][b] = (dq[j][b] + dq[j + 1][b / a]) % MD;
}
for (j = m - 1; j >= 0; j--) {
a = aa[i][j];
for (b1 = B - 1, b2 = 1, x = 0; b1 * a >= B; b1--) {
while (b2 < B && (long long) b1 * a * b2 < c)
x = (x + dq[j][b2++]) % MD;
ans = (ans + (long long) dp[i][j][b1] * x) % MD;
}
}
}
}
ans = (choose(n - 1 + m - 1, n - 1) - ans + MD) % MD;
printf("%d\n", ans);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |