ABC232E - Rook Path

考え方

$K$回の操作はシミュレーションしなくてはならない．

現在地を$(x,y)$で表し，$(x_{2}, y_{2})$を「ゴール」と呼ぶ．

各ステップに対して，状態としては

1. $x$座標も$y$座標も「ゴール」と関係ない：$x\neq x_{2}, y\neq y_{2}$
2. $x$座標のみ「ゴール」に一致：$x= x_{2}, y\neq y_{2}$
3. $y$座標のみ「ゴール」に一致：$x \neq x_{2}, y= y_{2}$
4. $x$座標も$y$座標も「ゴール」と一致：$x = x_{2}, y= y_{2}$

だけである．さらに，これら4つの状態の数がわかれば，次ステップの遷移方法を考えれば，状態数が計算できる．

上記のあるステップでの状態数を$s_{1},s_{2},s_{3},s_{4}$とすれば，次ステップの状態数は

\begin{aligned}
s^{\prime}_{1}
& = ( (H - 2) + (W - 2) ) \cdot s_{1} + (H - 1) \cdot s_{2} + (W - 1) \cdot s_{3} \\
s^{\prime}_{2}
& = s_{1} + (W - 2) \cdot s_{2} + (W - 1) \cdot s_{4} \\
s^{\prime}_{3}
& = s_{1} + (H - 2) \cdot s_{3} + (H - 1) \cdot s_{4} \\
s^{\prime}_{4}
& = s_{2} + s_{3}
\end{aligned}

と計算できる．

回答例

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
mod = 998244353

s1, s2, s3, s4 = 0, 0, 0, 0
if x1 == x2:
  if y1 == y2:
    s4 += 1
  else:
    s2 += 1
else:
  if y1 == y2:
    s3 += 1
  else:
    s1 += 1

for _ in range(K):
  s1, s2, s3, s4 = (
    (H - 2 + W - 2) * s1 + (H - 1) * s2 + (W - 1) * s3,
    s1 + (W - 2) * s2 + (W - 1) * s4,
    s1 + (H - 2) * s3 + (H - 1) * s4,
    s2 + s3)
  
  s1 %= mod
  s2 %= mod
  s3 %= mod
  s4 %= mod
  
print(s4)