제출 #703043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
703043		rainboy	힘 센 거북 (IZhO11_turtle)	C11	30 / 100	107 ms	7316 KiB

turtle

#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]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 100