Educational DP Contest / DP まとめコンテスト Y - Grid 2

解法

包除原理を用いて解きます。
$dp[i][j] =$ $j$ 個以上の壁を通り、 $i$ 番目の壁に到達するような通り方の場合の数
とします。ここで、壁について、行、列の順で昇順ソートしておくと、 $i$ 番目の壁を通る際に、 $i+1$ 番目以降の壁を先に通ることはありえなくなるので、うまく計算することができます。
また、スタート地点を $0$ 番目の壁、ゴール地点を $N+1$ 番目の壁、とすることで、初期化は $dp[0][0] = 1$ とすることができます。
$dp[i][j] = \sum dp[k][j-1] \times _{r_{i} + c_{i} - r_{k} - c_{k}} C _{r_{i}-r_{k}} ($ ただし、 $i \gt k, c_{i} \gt c_{k})$
$r_{i} \gt r_{k}$ は、初めにソートしたときに満たすようになっています。
右側のコンビネーションの項は、 $k$ 番目の壁から $i$ 番目の壁に行く行き方です。
これを計算すると、答えが $(偶数個の壁を通り(H,W)へ行く行き方)-(奇数個の壁を通り(H,W)へ行く行き方)$
となるので、 $dp[i][j]$ の $j$ の部分を、 $0,1$ の2通りに集約することができます。こうすることで、計算量が $O(N^{2})$ におさまり、
$dp[N+1][0] - dp[N+1][1]$
になります。