#include <stdio.h>
#define N 300000
#define M 300000
#define K 22
#define L 30 /* L = ceil(log2(10^9)) */
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int r, c, n, t, md;
int xx[K], yy[K], xx_[K], yy_[K];
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = xx[ii[j]] != xx[i_] ? xx[ii[j]] - xx[i_] : yy[ii[j]] - yy[i_];
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int x_, y_;
void gcd_(int a, int b) {
if (b == 0)
x_ = 1, y_ = 0;
else {
int tmp;
gcd_(b, a % b);
tmp = x_ - a / b * y_, x_ = y_, y_ = tmp;
}
}
int inv(int a, int md) {
gcd_(a, md);
if (x_ < 0)
x_ += md;
return x_;
}
int garner(int a0, int md0, int a1, int md1) {
a1 = (long long) (a1 - a0) * inv(md0 % md1, md1) % md1;
if (a1 < 0)
a1 += md1;
return a1 * md0 + a0;
}
int ff[N + M + 1], gg[N + M + 1], ee[N + M + 1], pp[L + 1];
int ww[K][K], dp[K][K], dq[K], md_;
void solve(int p, int q, int e_) {
int a, b, e, i, j, l;
ff[0] = gg[0] = 1, ee[0] = 0;
for (a = 1; a <= r + c; a++) {
b = a, e = 0;
while (b % p == 0)
b /= p, e++;
ff[a] = (long long) ff[a - 1] * b % q;
gg[a] = (long long) gg[a - 1] * inv(b, q) % q;
ee[a] = ee[a - 1] + e;
}
pp[0] = 1;
for (l = 1; l < e_; l++)
pp[l] = pp[l - 1] * p;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++) {
int x = xx[j] - xx[i], y = yy[j] - yy[i];
if (x < 0 || y < 0)
continue;
if (ee[x + y] - ee[x] - ee[y] >= e_)
continue;
ww[i][j] = garner(ww[i][j], md_, (long long) ff[x + y] * gg[x] % q * gg[y] % q * pp[ee[x + y] - ee[x] - ee[y]] % q, q);
}
md_ *= q;
}
int main() {
static int ii[K];
int i, j, k, p, q, e, ans;
scanf("%d%d%d%d%d", &r, &c, &n, &t, &md), n += 2, t++;
xx[0] = 0, yy[0] = 0;
for (i = 1; i < n - 1; i++)
scanf("%d%d", &xx[i], &yy[i]);
xx[n - 1] = r, yy[n - 1] = c;
for (i = 0; i < n; i++)
ii[i] = i;
sort(ii, 0, n);
for (i = 0; i < n; i++)
xx_[i] = xx[ii[i]], yy_[i] = yy[ii[i]];
for (i = 0; i < n; i++)
xx[i] = xx_[i], yy[i] = yy_[i];
md_ = 1;
for (p = 2; p <= md / p; p++)
if (md % p == 0) {
q = 1, e = 0;
while (md % p == 0)
md /= p, q *= p, e++;
solve(p, q, e);
}
if (md > 1)
solve(md, md, 1);
md = md_;
for (i = 0; i < n; i++) {
dp[i][i] = -1;
for (j = i; j < n; j++)
for (k = j + 1; k < n; k++)
dp[i][k] = (dp[i][k] - (long long) dp[i][j] * ww[j][k] % md + md) % md;
}
ans = 0;
dq[0] = 1;
while (t--) {
for (i = n - 1; i >= 0; i--) {
int x = dq[i];
if (x == 0)
continue;
dq[i] = 0;
for (j = i + 1; j < n; j++)
dq[j] = (dq[j] + (long long) x * dp[i][j]) % md;
}
ans = (ans + dq[n - 1]) % md;
}
printf("%d\n", ans);
return 0;
}
Compilation message
turtle.c: In function 'main':
turtle.c:101:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf("%d%d%d%d%d", &r, &c, &n, &t, &md), n += 2, t++;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.c:104:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | scanf("%d%d", &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
2 ms |
468 KB |
Output is correct |
| 11 |
Correct |
19 ms |
2600 KB |
Output is correct |
| 12 |
Correct |
62 ms |
7192 KB |
Output is correct |
| 13 |
Correct |
91 ms |
6080 KB |
Output is correct |
| 14 |
Correct |
35 ms |
2628 KB |
Output is correct |
| 15 |
Correct |
36 ms |
2592 KB |
Output is correct |
| 16 |
Correct |
106 ms |
6940 KB |
Output is correct |
| 17 |
Correct |
103 ms |
6632 KB |
Output is correct |
| 18 |
Correct |
117 ms |
7244 KB |
Output is correct |
| 19 |
Correct |
110 ms |
7304 KB |
Output is correct |
| 20 |
Correct |
112 ms |
7332 KB |
Output is correct |
