EDPC Y - Grid 2

グリッド2

考え方

ABCでいうと、F問題級。

壁を通らない道順は、全ての通り方から壁を少なくとも $1$ つ通る道順を引けばよい。
それは包除原理より、以下でよい。

全道順
- 指定の壁1つを通る（他は不問）道順×その壁の指定のパターン数分
+ 指定の壁2つを通る（他は不問）道順×その壁の指定のパターン数分
- 指定の壁3つを通る（他は不問）道順×その壁の指定のパターン数分
+ ……

これをもう少しまとめると、次のようになる。

指定の壁偶数個を通る（他は不問）道順×その壁の指定のパターン数分
- 指定の壁奇数個を通る（他は不問）道順×その壁の指定のパターン数分

そこで、スタートとゴールと壁をまとめて注目点としたうえで、各点について以下を求めればよい。

前者は、自分より左上にある全ての点の、「その点までの奇数個の道順 $\times$ その点からの道順」の合計。
その点からの道順は、Comb(移動回数, 右への移動の回数) でよい。
後者も同様。
これで、ゴールマスについて前述の計算をすればよい。

計算量は前処理を除いて $O(N^2)$。

入力を受け取る。

h: 3
w: 4
n: 2
壁:
  (2, 2)
  (1, 4)

スタート・壁・ゴールを注目点とする。
右または下にしか進めないので、座標順に並べた注目点から順に考えればよい。

(1, 1) スタート
(1, 4) 壁
(2, 2) 壁
(3, 4) ゴール

包除原理の符号を管理するため、スタートから各注目点までの道順を2種類に分ける。

スタートと現在の注目点を含め、指定した注目点の個数が奇数であるものと偶数であるものを別に数える。

スタートだけを指定した状態は $1$ 通りなので、スタートでは奇数側が $1$、偶数側が $0$ である。

次に壁 $(1,4)$ を考える。

スタートからは右へ $3$ 回進むだけなので、${}_{3}\mathrm{C}_{3}=1$ 通りである。

新しい注目点を1つ追加するので偶奇が反転する。
したがって、この壁では偶数側が $1$ 通りとなる。

壁 $(2,2)$ については、スタートから下へ $1$ 回、右へ $1$ 回進むので、${}_{2}\mathrm{C}_{1}=2$ 通りである。

$(1,4)$ から $(2,2)$ へは左に戻る必要があるため、この2点を続けて通ることはできない。

したがって、$(2,2)$ では偶数側が $2$ 通りとなる。

最後にゴール $(3,4)$ を考える。

スタートから直接ゴールへ進む方法は、${}_{5}\mathrm{C}_{3}=10$ 通りである。
注目点を1つ追加するので、これは偶数側へ $10$ 通り加わる。

壁 $(1,4)$ からゴールへは、下へ $2$ 回進むだけなので $1$ 通りである。
この壁までの偶数側 $1$ 通りから遷移するので、ゴールの奇数側へ $1$ 通り加わる。

壁 $(2,2)$ からゴールへは、下へ $1$ 回、右へ $2$ 回進む。
道順は ${}_{3}\mathrm{C}_{2}=3$ 通りである。

この壁までの偶数側は $2$ 通りなので、ゴールの奇数側へ $2\times3=6$ 通り加わる。

よってゴールでは、次の値になる。

偶数側: 10
奇数側: 1 + 6 = 7

一般には、ある注目点について、そこより左上にある全ての注目点から遷移させる。

2点間で下へ $d_r$ 回、右へ $d_c$ 回進むなら、その間の道順は ${}_{d_r+d_c}\mathrm{C}_{d_c}$ 通りである。
この値を掛けて、偶数側から奇数側へ、奇数側から偶数側へ加える。

最後に包除原理の符号を反映し、ゴールの偶数側から奇数側を引く。
$10-7=3$ なので、答えは $3$。

答えは $10^9+7$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
二項係数の計算では階乗の逆元が必要になるため、$10^9+7$ が素数であることを利用し、逆元は $10^9+7-2$ 乗として求める。
累乗計算には繰り返し二乗法を用いること。

特になし。