ABC042 D - いろはちゃんとマス目 / Iroha and a Grid
解法
modとコンビネーションが出てくるので、例によって逆元の知識を使用します。
例によってけんちょんさんの記事を載せておきます。
問題の条件を図で表すと次のようになります。
Sがスタートの位置、Gがゴールの位置で、黒く塗りつぶされているのが通れない部分です。
そして、必ず通る部分、と書かれているのが文字通り必ず通る部分になります。
Sから縦にマス、横に
マス以上
マス以下移動したのがこの部分です。
この部分のうち少なくとも1つのマスを通らないとゴールへ行くことはできません。
ということで、この部分を利用して、SからGへ行く方法を重複なく数えていきます。
必ず通る部分を1つ決めたときのSからGへの行き方を決めます。
Sから縦にマス、横に
マス移動した場合を考えます。このマスをPと名付けます。
そもそもSからGにいくには縦にマス、横に
マス移動する必要があることから、
今いるPからGへ行くには、縦にマス、横に
マス移動する必要があります。
Pを通ってSからGへ行く方法を考えるとき、黒く塗られた通行不可の部分は必ず通らないので(そこを通るルートを考えると最短距離ではなくなります)、 純粋に
(SからPへ行く場合の数)×(PからGへ行く場合の数)
を求めてあげると、求めたい場合の数になります。
また、純粋な長方形のマス目について、左上から右下へいく行き方は、
(縦に移動する回数＋横に移動する回数)から(横に移動する回数)の選び方(もしくは縦に移動する回数の選び方)
ということで、
が、Pを通ってSからGに行く行き方となります。
さて、あとはについて全探索、といきたいところですがそれでは被りが発生してしまいます。
Pにいく方法を数えたときに、Pの1つ左から移動してくるパターンが存在しますが、これはPの1つ左のマスで計算した時点で既に数え終えています。ということで、重複が発生します(左端を除く)。
ということで、左端以外は、次のような式になります。
あとは、について全探索して、和を求めていけば答えとなります。
