제출 #703043

#제출 시각아이디문제언어결과실행 시간메모리
703043rainboy힘 센 거북 (IZhO11_turtle)C11
30 / 100
107 ms7316 KiB
#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] + x * dp[i][j]) % md; } ans = (ans + dq[n - 1]) % md; } printf("%d\n", ans); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

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 timeMemoryGrader output
Fetching results...