No.2802 Pill Bug in Grid Maze
タグ : / 解いたユーザー数 22
作問者 : 👑
![Magentor](https://pbs.twimg.com/profile_images/1715389554197495808/7HlNzj_p.jpg)
![Lucagon](https://pbs.twimg.com/profile_images/1739313456279670784/Og8zrEy8.jpg)
問題文
ゆきこーだー地方にはダンゴムシが生息しています。
ダンゴムシを のグリッド上で移動させることを考えます。
グリッドの上から 番目、左から 番目のマスをマス と書きます。
なお、 の範囲外のマスには全て障害物があるものとして扱います。
- 向いている方向に隣接するマスに障害物がなかった場合、そのマスに移動する。
- 奇数回目に障害物にぶつかった場合、向いている方向を右向きに 回転する。
- 偶数回目に障害物にぶつかった場合、向いている方向を左向きに 回転する。
「障害物にぶつかる」をより厳密に言うと、向いている方向に隣接するマスが障害物が置かれていることを指します。
さて、グリッドのマスを 個以上選び、選んだマスに障害物を置くことで迷路を作ることを考えます。
生成できる異なる迷路は 個ありますが、そのうち次の条件を満たす迷路は何個ありますか?
- マス とマス には障害物が置いていない。
- 始め、ダンゴムシをマス に右向きに置く。そのとき、ダンゴムシは有限回の行動によってマス まで到達することが可能である。
答えが非常に大きくなる場合があるので、 で割った余りを求めてください。
制約
- は整数
入力
入力は以下の形式で標準入力から与えられる。
出力
条件を満たす迷路の個数を で割った余りを出力せよ。
サンプル
サンプル1
入力
4 5
出力
28672
例えば、このような迷路は条件を満たします。このように条件を満たす迷路が 個存在します。
逆に、このような迷路はダンゴムシの生態ではマス でスタックしてしまうため、条件を満たしません。
サンプル2
入力
6 1
出力
1
グリッド内のどのマスにも障害物を置いていない迷路のみが条件を満たします。
サンプル3
入力
100 100
出力
865485495
で割った余りを求めてください。
サンプル4
入力
1920 1080
出力
512501559
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。