問題一覧 > 通常問題

No.3600 Moving Queen Many Times

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 25
作問者 : 👑 AngrySadEight / テスター : gomaazarasi ぽえ
ProblemId : 13484 / yukicoder contest 506 裏・クイーンコンテスト (順位表) / 自分の提出
問題文最終更新日: 2026-07-24 22:25:00
yukicoder contest 506 裏・クイーンコンテストの他の問題:

問題文

縦 $H$ マス，横 $W$ マスのマス目があります．上から $i(1 \leq i \leq H)$ 番目，左から $j(1 \leq j \leq W)$ 番目のマスを，マス $(i, j)$ と表記します．

最初，マス $(sx, sy)$ に，クイーンのコマがあります．クイーンのコマは，マス目の範囲内のマスに自由に出入り可能ですが，範囲外のマスには出入りできません．

これから，あなたは今クイーンのコマがあるマスから移動可能なマスを $1$ つ選んで移動することを，$K$ 回繰り返します．ただし，移動の際には以下の条件を満たす必要があります．

  • $C_k(i, j)$ を，$1$ 回目の移動から $k$ 回目の移動までに，マス $(i, j)$ を移動先として選んだ回数とする（この回数には，最初にクイーンのコマがいた $(sx, sy)$ は計上されない）．このとき，$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$ が成り立つ．

この条件を満たす移動方法のうち，$K$ 回の移動後にクイーンのコマがマス $(gx, gy)$ にあるものの数を，$998244353$ で割った余りを求めてください．

なお，$2$ つの移動方法は，ある $k$ が存在し，$k$ 回目に移動先として選んだマスがその $2$ つの移動方法の間で異なる場合に区別されます．

クイーンのコマの移動方法について（クリックで開く）

クイーンのコマは，$1$ 回の移動において，縦・横・斜めの方向に，通る経路のマスが全て出入り可能である限り自由なマス数進むことができます．ただし，今いるマスにとどまることを $1$ 回の移動とみなすことはできません．厳密には，マス $(i, j)$ にあるクイーンのコマは次のような移動が可能です．

  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i, j + k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i, j + l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i, j - k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i, j - l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j + k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j + l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j - k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j - l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j + k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j + l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j - k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j - l)$ はクイーンのコマが出入り可能なマスである．

制約

  • 入力は全て整数
  • $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}$

入力

入力は以下の形式で標準入力から与えられる．

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

出力

答えを出力せよ．

サンプル

サンプル1
入力
2 2 1 1 1 2 2
出力
2

マス $(1, 1)$ から $2$ 回の移動でマス $(1, 2)$ へたどり着く方法は，次の $2$ 通りがあります．

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

このどちらの移動方法の場合も，$k = 1, 2$ において $\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$ を満たすため，条件を満たします．

サンプル2
入力
3 3 1 1 3 3 3
出力
23

例えば，次の移動方法は条件を満たします．

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

このような移動方法は，上記の方法を含めて $23$ 通りあります．

次の移動方法は，$k = 3$ において $\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$ を満たさないため，$23$ 通りに含まれません．

  • $(1, 1) \rightarrow (3, 3) \rightarrow (1, 1) \rightarrow (3, 3)$
サンプル3
入力
4 4 1 2 3 4 123456789
出力
123795037

$998244353$ で割った余りを出力してください．

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