oj.uz

답안 #703044

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
703044 2023-02-25T18:41:25 Z rainboy 힘 센 거북 (IZhO11_turtle) C
100 / 100
 117 ms 7332 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] + (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]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 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