問題一覧 > 通常問題

No.2802 Pill Bug in Grid Maze

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 22
作問者 : 👑 loop0919loop0919 / テスター : MagentorMagentor hiro1729hiro1729 👑 獅子座じゃない人獅子座じゃない人 LucagonLucagon Basin-BugBasin-Bug mitu24472mitu24472
1 ProblemId : 10256 / 自分の提出
問題文最終更新日: 2024-07-10 15:21:00

問題文

ゆきこーだー地方にはダンゴムシが生息しています。

ダンゴムシを H×WH \times W のグリッド上で移動させることを考えます。 グリッドの上から ii 番目、左から jj 番目のマスをマス (i,j)(i, j) と書きます。
なお、H×WH \times W の範囲外のマスには全て障害物があるものとして扱います。

ダンゴムシは次の行動を永久に繰り返す生態を持っています。

  • 向いている方向に隣接するマスに障害物がなかった場合、そのマスに移動する。
  • 奇数回目に障害物にぶつかった場合、向いている方向を右向き90°90° 回転する。
  • 偶数回目に障害物にぶつかった場合、向いている方向を左向き90°90° 回転する。

「障害物にぶつかる」をより厳密に言うと、向いている方向に隣接するマスが障害物が置かれていることを指します。

さて、グリッドのマスを 00 個以上選び、選んだマスに障害物を置くことで迷路を作ることを考えます。
生成できる異なる迷路は 2HW2^{HW} 個ありますが、そのうち次の条件を満たす迷路は何個ありますか?

  • マス (1,1)(1, 1) とマス (H,W)(H, W) には障害物が置いていない。
  • 始め、ダンゴムシをマス (1,1)(1, 1) に右向きに置く。そのとき、ダンゴムシは有限回の行動によってマス (H,W)(H, W) まで到達することが可能である。

答えが非常に大きくなる場合があるので、998244353998244353 で割った余りを求めてください。

制約

  • H,WH, W は整数
  • 1H,W2×1051 \leq H, W \leq 2 \times 10^5

入力

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

H WH\ W

出力

条件を満たす迷路の個数を 998244353998244353 で割った余りを出力せよ。

サンプル

サンプル1
入力
4 5
出力
28672

例えば、このような迷路は条件を満たします。このように条件を満たす迷路が 2867228672 個存在します。


逆に、このような迷路はダンゴムシの生態ではマス (2,5)(2, 5) でスタックしてしまうため、条件を満たしません。

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

グリッド内のどのマスにも障害物を置いていない迷路のみが条件を満たします。

サンプル3
入力
100 100
出力
865485495

998244353998244353 で割った余りを求めてください。

サンプル4
入力
1920 1080
出力
512501559

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