DPまとめコンテスト/Y - Grid 2 - 競技プログラミング用 知識集積所【7/25更新】

---

問題

DP-Y

必要知識

ABCのB以下レベルの内容は省略

• 動的計画法
• 順列組み合わせ（未作成）
• 包除原理（未作成）
• 剰余類環
• 繰り返し二乗法（未作成）

考え方

壁を通らない道順は、全ての通り方から壁を少なくとも1つ通る道順を引けばよい。
それは包除原理（未作成）より、

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

でよい。

これをもう少しまとめると

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

でよいことがわかる。

そこで、スタートとゴールも壁一覧に加えてしまったうえで、各壁について

• スタートからそこまで、指定の壁偶数個を通る（他は不問）道順の総数
• スタートからそこまで、指定の壁奇数個を通る（他は不問）道順の総数

を順番に求めていけばよい。

前者は、自分より左上にある全ての壁について、「その壁までの奇数個の道順*その壁からの道順」を合計すればよい。
その壁からの道順は、Comb(移動回数,右への移動の回数)でよい。
後者も同様。

答えはmod10^9+7での値なので、剰余類環も参照。
高速化のため、h+w-1までの階乗の一覧を全てメモ化（未作成）し、繰り返し二乗法（未作成）で逆元も全てメモ化（未作成）しておくこと。

解答例

解答例

注意点

別解