제출 #545939

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545939		rainboy	Chess Rush (CEOI20_chessrush)	C11	100 / 100	292 ms	8120 KiB

chessrush

/* https://codeforces.com/blog/entry/82022?#comment-687998 (Benq) */
#include <stdio.h>
#include <string.h>

#define N	1000
#define MD	1000000007

int abs_(int a) { return a > 0 ? a : -a; }

int vv[N + 1];

void init() {
	int i;

	for (i = 1; i <= N; i++)
		vv[i] = i == 1 ? 1 : (long long) vv[i - MD % i] * (MD / i + 1) % MD;
}

int choose(int n, int k) {
	return k == 0 ? 1 : (long long) choose(n - 1, k - 1) * n % MD * vv[k] % MD;
}

void apply(int dp[][N], int n) {
	static int aa[N];
	int i, j;

	for (i = 0; i < n; i++) {
		memcpy(aa, dp[i], n * sizeof *dp[i]);
		for (j = 0; j < n; j++)
			dp[i][j] = ((long long) (j == 0 ? 0 : aa[j - 1]) + aa[j] + (j + 1 == n ? 0 : aa[j + 1])) % MD;
	}
}

void square(int dp[][N], int n) {
	static int dq[N][N];
	int i, j;

	for (i = 0; i < n; i++)
		memset(dq[i], 0, n * sizeof *dq[i]);
	for (j = 0; j < n; j++)
		for (i = 0; i < n; i++)
			dq[0][j] = (dq[0][j] + (long long) dp[0][i] * dp[i][j]) % MD;
	for (i = 0; i < n; i++)
		dq[i][0] = dq[0][i];
	for (i = 1; i < n; i++)
		for (j = 1; i + j < n; j++)
			dq[i][j] = (dq[i - 1][j - 1] + dq[0][i + j]) % MD;
	for (i = 0; i < n; i++)
		for (j = 0; i + j < n; j++)
			dq[n - 1 - i][n - 1 - j] = dq[i][j];
	for (i = 0; i < n; i++)
		memcpy(dp[i], dq[i], n * sizeof *dq[i]);
}

void power(int dp[][N], int n, int k) {
	if (k == 0) {
		int i, j;

		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				dp[i][j] = i == j;
		return;
	}
	power(dp, n, k / 2);
	square(dp, n);
	if (k & 1)
		apply(dp, n);
}

int dist(int m, int j1, int i2, int j2) {
	int d = i2 / (m - 1);

	if (d % 2 == 0 && i2 % (m - 1) > abs_(j1 - j2) || d % 2 == 1 && i2 % (m - 1) > abs_(m - 1 - j1 - j2))
		d++;
	return d + 1;
}

int main() {
	static int dp[N][N];
	int n, m, q;

	init();
	scanf("%d%d%d", &n, &m, &q);
	power(dp, m, n - 1);
	while (q--) {
		static char s[2];
		int j1, j2;

		scanf("%s%d%d", s, &j1, &j2), j1--, j2--;
		if (s[0] == 'P') {
			if (j1 == j2)
				printf("%d 1\n", n - 1);
			else
				printf("0 0\n");
		} else if (s[0] == 'R') {
			if (j1 == j2)
				printf("1 1\n");
			else
				printf("2 2\n");
		} else if (s[0] == 'Q') {
			if (j1 == j2 || n == m && (j1 == 0 && j2 == m - 1 || j1 == m - 1 && j2 == 0))
				printf("1 1\n");
			else {
				int cnt;

				cnt = 4;
				if (n == m && (j1 == 0 || j1 == m - 1 || j2 == 0 || j2 == m - 1))
					cnt++;
				if (j1 % 2 == (n - 1 - j2) % 2) {
					int i_, j_;

					i_ = ((0 + j1) + (n - 1 - j2)) / 2, j_ = ((0 + j1) - (n - 1 - j2)) / 2;
					if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m)
						cnt++;
					i_ = ((0 - j1) + (n - 1 - j2)) / 2, j_ = ((n - 1 - j2) - (0 - j1)) / 2;
					if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m)
						cnt++;
				}
				printf("2 %d\n", cnt);
			}
		} else if (s[0] == 'B') {
			if (j1 % 2 != (n - 1 - j2) % 2) {
				printf("0 0\n");
			} else if ((j1 == 0 && j2 == 0 || j1 == m - 1 && j2 == m - 1)
					&& ((n - 1) % ((m - 1) * 2) == 0)
					|| (j1 == 0 && j2 == m - 1 || j1 == m - 1 && j2 == 0)
					&& ((n - 1) % ((m - 1) * 2)) == m - 1) {
				printf("%d 1\n", (n - 1) / (m - 1));
			} else {
				int d = dist(m, j1, n - 1, j2), k, x, y;

				if (d % 2 == 1) {
					k = 0;
					if ((x = n - 1 + j2) <= (y = (m - 1) * (d - 1) + j1 + 0))
						k = (k + choose((y - x) / 2 + d - 2, (y - x) / 2)) % MD;
					if ((x = n - 1 - j2) <= (y = (m - 1) * (d - 1) + m - 1 - j1 - (m - 1)))
						k = (k + choose((y - x) / 2 + d - 2, (y - x) / 2)) % MD;
				} else {
					k = 0;
					if ((x = n - 1 + j2) <= (y = (m - 1) * (d - 1) + m - 1 - j1 + 0))
						k = (k + choose((y - x) / 2 + d - 2, (y - x) / 2)) % MD;
					if ((x = n - 1 - j2) <= (y = (m - 1) * (d - 1) + j1 - (m - 1)))
						k = (k + choose((y - x) / 2 + d - 2, (y - x) / 2)) % MD;
				}
				printf("%d %d\n", d, k);
			}
		} else
			printf("%d %d\n", n - 1, dp[j1][j2]);
	}
	return 0;
}

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

chessrush.c: In function 'dist':
chessrush.c:73:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   73 |  if (d % 2 == 0 && i2 % (m - 1) > abs_(j1 - j2) || d % 2 == 1 && i2 % (m - 1) > abs_(m - 1 - j1 - j2))
      |      ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
chessrush.c: In function 'main':
chessrush.c:101:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  101 |    if (j1 == j2 || n == m && (j1 == 0 && j2 == m - 1 || j1 == m - 1 && j2 == 0))
      |                               ~~~~~~~~^~~~~~~~~~~~~~
chessrush.c:101:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  101 |    if (j1 == j2 || n == m && (j1 == 0 && j2 == m - 1 || j1 == m - 1 && j2 == 0))
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
chessrush.c:124:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  124 |    } else if ((j1 == 0 && j2 == 0 || j1 == m - 1 && j2 == m - 1)
      |                ~~~~~~~~^~~~~~~~~~
chessrush.c:126:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  126 |      || (j1 == 0 && j2 == m - 1 || j1 == m - 1 && j2 == 0)
      |          ~~~~~~~~^~~~~~~~~~~~~~
chessrush.c:125:6: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  124 |    } else if ((j1 == 0 && j2 == 0 || j1 == m - 1 && j2 == m - 1)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  125 |      && ((n - 1) % ((m - 1) * 2) == 0)
      |      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
chessrush.c:83:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d%d%d", &n, &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
chessrush.c:89:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   scanf("%s%d%d", s, &j1, &j2), j1--, j2--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 22 / 22
• Subtask 5: 5 / 5
• Subtask 6: 8 / 8
• Subtask 7: 15 / 15
• Subtask 8: 20 / 20
• Subtask 9: 7 / 7