oj.uz

답안 #703043

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
703043 2023-02-25T18:40:47 Z rainboy 힘 센 거북 (IZhO11_turtle) C
30 / 100
 107 ms 7316 KB 
#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;
}

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

Subtask #1
30.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 292 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 0 ms 296 KB Output isn't correct
7 Incorrect 1 ms 296 KB Output isn't correct
8 Incorrect 0 ms 300 KB Output isn't correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Incorrect 2 ms 468 KB Output isn't correct
11 Incorrect 19 ms 2592 KB Output isn't correct
12 Correct 55 ms 7224 KB Output is correct
13 Incorrect 91 ms 6148 KB Output isn't correct
14 Incorrect 34 ms 2632 KB Output isn't correct
15 Incorrect 35 ms 2632 KB Output isn't correct
16 Incorrect 100 ms 6944 KB Output isn't correct
17 Correct 97 ms 6800 KB Output is correct
18 Incorrect 107 ms 7212 KB Output isn't correct
19 Incorrect 106 ms 7316 KB Output isn't correct
20 Incorrect 107 ms 7312 KB Output isn't correct