問題一覧 > 通常問題

No.3600 Moving Queen Many Times

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 28
作問者 : 👑 AngrySadEight / テスター : gomaazarasi ぽえ
お気に入りにしたユーザー ProblemId : 13484 / 自分の提出
問題文最終更新日: 2026-07-24 22:25:00
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 506 裏・クイーンコンテスト (順位表) の他の問題:

Problem Statement

There is a grid with $H$ rows and $W$ columns. The square in the $i(1 \leq i \leq H)$-th row from the top and the $j(1 \leq j \leq W)$-th column from the left is denoted by square $(i, j)$.

Initially, a queen piece is on square $(sx, sy)$. The queen piece can freely enter and leave squares within the grid, but cannot enter or leave squares outside the grid.

You will now repeat the following $K$ times: choose $1$ square that the queen piece can move to from its current square, and move it there. However, the moves must satisfy the following condition.

  • Let $C_k(i, j)$ be the number of times square $(i, j)$ was chosen as the destination from the $1$-st move through the $k$-th move (this count does not include $(sx, sy)$, where the queen piece was initially placed). Then, for $k = 1, 2, \dots, K$, $\displaystyle \max_{1 \leq i \leq H, 1 \leq j \leq W}C_k(i, j) - \displaystyle \min_{1 \leq i \leq H, 1 \leq j \leq W}C_k(i, j) \leq 1$ holds.

Among the ways of moving that satisfy this condition, find the number of those in which the queen piece is on square $(gx, gy)$ after the $K$ moves, modulo $998244353$.

Here, $2$ ways of moving are considered different if there exists some $k$ such that the square chosen as the destination of the $k$-th move differs between those $2$ ways of moving.

About how the queen piece moves (click to open)

In $1$ move, the queen piece can advance any number of squares vertically, horizontally, or diagonally, as long as all squares on its path can be entered and left. However, staying on the current square does not count as $1$ move. Strictly speaking, a queen piece on square $(i, j)$ can make the following moves.

  • For a positive integer $k$, it can move to square $(i, j + k)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, square $(i, j + l)$ is a square that the queen piece can enter and leave.
  • For a positive integer $k$, it can move to square $(i, j - k)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, square $(i, j - l)$ is a square that the queen piece can enter and leave.
  • For a positive integer $k$, it can move to square $(i + k, j)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, square $(i + l, j)$ is a square that the queen piece can enter and leave.
  • For a positive integer $k$, it can move to square $(i - k, j)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, square $(i - l, j)$ is a square that the queen piece can enter and leave.
  • For a positive integer $k$, it can move to square $(i + k, j + k)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, square $(i + l, j + l)$ is a square that the queen piece can enter and leave.
  • For a positive integer $k$, it can move to square $(i + k, j - k)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, square $(i + l, j - l)$ is a square that the queen piece can enter and leave.
  • For a positive integer $k$, it can move to square $(i - k, j + k)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, square $(i - l, j + l)$ is a square that the queen piece can enter and leave.
  • For a positive integer $k$, it can move to square $(i - k, j - k)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, square $(i - l, j - l)$ is a square that the queen piece can enter and leave.

Constraints

  • All input values are integers.
  • $2 \leq H \leq 4$
  • $2 \leq W \leq 4$
  • $1 \leq sx, gx \leq H$
  • $1 \leq sy, gy \leq W$
  • $1 \leq K \leq 10^{18}$

Input

The input is given from standard input in the following format.

$H$ $W$ $sx$ $sy$ $gx$ $gy$ $K$

Output

Output the answer.

Sample

Sample 1
Input
2 2 1 1 1 2 2
Output
2

From square $(1, 1)$, in $2$ moves, square $(1, 2)$ can be reached in the following $2$ ways.

  • $(1, 1) \rightarrow (2, 1) \rightarrow (1, 2)$
  • $(1, 1) \rightarrow (2, 2) \rightarrow (1, 2)$

Both of these ways of moving satisfy $\displaystyle \max_{1 \leq i \leq H, 1 \leq j \leq W}C_k(i, j) - \displaystyle \min_{1 \leq i \leq H, 1 \leq j \leq W}C_k(i, j) \leq 1$ for $k = 1, 2$, so they satisfy the condition.

Sample 2
Input
3 3 1 1 3 3 3
Output
23

For example, the following way of moving satisfies the condition.

  • $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 3)$

There are $23$ such ways of moving, including the one above.

The following way of moving does not satisfy $\displaystyle \max_{1 \leq i \leq H, 1 \leq j \leq W}C_k(i, j) - \displaystyle \min_{1 \leq i \leq H, 1 \leq j \leq W}C_k(i, j) \leq 1$ at $k = 3$, so it is not included in the $23$ ways.

  • $(1, 1) \rightarrow (3, 3) \rightarrow (1, 1) \rightarrow (3, 3)$
Sample 3
Input
4 4 1 2 3 4 123456789
Output
123795037

Output the remainder when divided by $998244353$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。