まず、第一に思い浮かぶ方針としてナイーブな \(\mathrm{O}(N^2)\) の DP 解法を高速化する方針が考えられますが、これはあまり容易ではなさそうです。(実はこの方針でも分割統治と組み合わせれば解けますがここでは触れません) そこで、はじめに問題を言い換えてみます。

具体的には、問題を次のように言い換えます。(以降ではこの言い換えた問題について考察しています。)

• \(N \times N\) のグリッドがある。
• \((a_1, b_1), \dots, (a_M, b_M)\) は壁マスである。
• また、\((1, 3), (2, 3), (3, 5), (4, 5), \dots, (n, \left\lceil \frac{n}{2} \right \rceil \times 2 + 1), \dots, (N-2, N-1)\) に、新たに追加された壁マスを置く。
• \((1, 1)\) から \((N, N)\) への壁マスを通らない最短経路は何通り？

問題をこのように言い換えると、EDPC Y問題 : Grid 2 として有名でもある、包除原理を適用した \(\mathrm{O}((N + M)^2)\) 解法を案出することが出来ます。
この解法を簡潔に説明します。まず、壁マスが通れないマスであるという設定は一旦忘れます。壁マスの集合を \(S\) とします。また、壁マスの集合 \(S\) に対して \(f(S)\) を次のように定義します。

• \(f(S)\) \(:=\) (壁マスのうち少なくとも \(S\) に含まれる壁マスを通って\((1,1)\) から \((N,N)\) へ最短経路で行く通り数)

とします。この時、求めたい答え \(X\) は包除原理により

\[X = \sum_{T \subseteq S} (-1)^{|T|} f(T)\]

になるので、この値を DP を用いて計算することを考えます。
壁マスをトポロジカル順に並べたものを \(w_1, w_2, \dots, w_{|S|}\) とします。また、\(f_i(S), \mathrm{dp}_i, g(a, b)\) を次のように定義します。

• \(f_i(S)\) \(:=\) (\(\lbrace w_1, w_2, \dots, w_{i-1} \rbrace\) のうち少なくとも \(S\) に含まれる壁マスを通って\((1,1)\) から \(w_i\) へ最短経路で行く通り数)
• \(\mathrm{dp}_i\) \(:=\) \(\displaystyle \sum_{T \subseteq \lbrace w_1, w_2, \dots, w_{i-1} \rbrace} f_i(T) (-1)^{|T| + 1}\)
• \(g(a, b)\) \(:=\) : \(a\) から \(b\) へ最短経路で移動する通り数

このように定義すると、\(\mathrm{dp}_i\) は 「最後に通った壁マスがどの位置か？」について考えることで \(\mathrm{dp}_j\) を用いて次の式で表すことが出来ます。

\[\mathrm{dp}_i = - g((1,1), w_i) - \sum_{j=1}^{i-1} g(w_j, w_i) \times \mathrm{dp}_j\]

同様の考察により求めたい答え \(X\) は次の式で表せます。

\[X = g((1,1),(N,N)) + \sum_{i=1}^{|S|} g(w_i, (N,N)) \times \mathrm{dp}_j\]

簡単のため \(w_0 = (1, 1), w_{|S| + 1} = (N, N)\) と定義して DP を \(0 \leq i \leq |S| + 1\) の範囲に拡張すると遷移がシンプルになって、

\[\mathrm{dp}_0 = 1\]

\[\mathrm{dp}_i = -\sum_{j=0}^{i-1} g(w_j, w_i) \times \mathrm{dp}_j\]

\[X = -\mathrm{dp}_{|S| + 1}\]

となります。以上の DP を計算することでこの問題を \(\mathrm{O}(|S|^2 + N) = \mathrm{O}((N+M)^2)\) で解くことが出来ます。

この DP を上手く高速化する方法を考えてみます。
壁マスは「元々あった壁マス」と「新たに追加した壁マス」の 2 種類があり、この 2 つを別々に考えることにします。元々からあった壁マスは \(M\) マス \((\leq 50)\) しかないので、計算量への寄与は\(\mathrm{O}(M(N+M))\) と小さく、元々あった壁マスが関連する遷移は愚直に計算しても問題ないです。一方、新しい壁マスから新しい壁マスへの遷移は \(\mathrm{O}(N^2)\) かかるのでこの部分を高速化できるとよさそうです。

新たに追加した壁マスのうち、

• \((2n - 1, 2n + 1)\) に追加した壁マスを \(w_{n, 1}\)
• \((2n, 2n + 1)\) に追加した壁マスを \(w_{n, 2}\)

と呼ぶことにします。全ての壁マスをトポロジカル順に列挙すると \(w_{1,1}, w_{1,2}, \dots, w_{N/2-1, 1}, w_{N/2-1,2}\) となります。このとき、\(w_{i,\ast}, w_{j,\ast}\) \((i \gt j)\) の間には

\[ \begin{aligned} g(w_{j,2}, w_{i,1}) &= \binom{4(i-j)-1}{2(i-j)}\\ g(w_{j,1}, w_{i,1}) = g(w_{j,2}, w_{i,2}) &= \binom{4(i-j)}{2(i-j)}\\ g(w_{j,1}, w_{w_2}) &= \binom{4(i-j)+1}{2(i-j)} \end{aligned} \]

という関係式が成り立ち、右辺はすべて \((i - j)\) の式として表せることがわかります。

\(w_{i,\ast}\) に関する DP テーブルの値を \(\mathrm{dp}_{i,\ast}\) と表すことにすると、\(\mathrm{dp}_{i,\ast}\) に対する \(\mathrm{dp}_{j, \ast}\) \((i \gt j)\) の寄与は

\[\mathrm{dp}_{i,1} \gets \mathrm{dp}_{i,1} -\sum_{j \lt i} \left(\mathrm{dp}_{j,1} \times g(w_{j,1}, w_{i, 1}) + \mathrm{dp}_{j, 2} \times g(w_{j,2}, w_{i,1})\right)\]

\[\mathrm{dp}_{i,2} \gets\mathrm{dp}_{i,2}- \sum_{j \lt i} \left(\mathrm{dp}_{j,1} \times g(w_{j,1}, w_{i, 2}) + \mathrm{dp}_{j, 2} \times g(w_{j,2}, w_{i,2})\right)\]

ですが、\(g(w_{j,\ast}, w_{i, \ast})\) はすべて \((i-j)\) の式なので上の右辺の式は畳み込みの形になっていることが分かります。よって、この遷移は分割統治 FFT が出来る形です。(分割統治 FFT については ABC213 Ex の解説 を参照してください。)

よって、新たに追加した壁マス同士の遷移は分割統治 FFT により \(\mathrm{O}(N \log^2 N)\) で計算できます。以上よりこの問題を \(\mathrm{O}(N \log^2 N + M(N + M))\) で解くことが出来て、これは十分高速です。

• 実装例, C++

Bonus: 想定解ではグリッドが階段状の形をしていることを利用しましたが、実はグリッドの形がどんな形であったとしても、(例えば楕円形や星形だったとしても、) 穴のないグリッドでさえあればこの問題を同じ計算量、\(\mathrm{O}(N \log^2 N + M(N + M))\) で解くことが出来ます。(グリッド自体が \(\mathrm{O}(N)\) 程度の情報で表現可能な形であることは前提とします) 興味がある方は考えてみましょう。(参考となるブログ)