本解説では以下の問題を考えます。

\(N\times N\) のグリッドに \(M\) 個の壁マスがある。下or右への移動を繰り返して、壁マスを通らずに \((0,0)\) から \((N-1,N-1)\) へ移動する経路数を求めよ。

この問題を、計算量 \(O((N+M)\sqrt{N\log{N}})\) で解きます。元の問題に立ち返るには、階段状の境界の外側に壁マスがあると思えばよいです。

マスの座標を \((r,c)\mapsto (r+c,c)\) と変換することで、できる移動は \((r,c)\to (r+1,c) \text{ or } (r+1,c+1)\) となります。求める経路は \((0,0)\) から \((2N-2,N-1)\) への移動経路です。

\[a_{r,c}\coloneqq (0,0)\text{ から }(r,c)\text{ まで壁マスを通らずに移動する経路数}\]

とします。ただし、\((r,c)\) が壁マスの時は \(a_{r,c}=0\) とします。また、その母関数を

\[f_r(X)=\sum_{c}a_{r,c}X^c\]

とします。

\(L<R\) に対し、\(f_L\) が既知の状態で \(f_R\) を求めることを考えます。障害物がない場合、

\[f_R(X)=f_L(X)(1+X)^{R-L}\]

と計算することができます。ここから障害物による寄与を引いていきます。

区間 \(I\) に対して、\(r\) 座標が \(I\) に含まれる壁マスの集合を \(W_I\) とします。

\(w\in W_{(L,R)}\) に対して、

\[b_w\coloneqq(0,0)\text{ から移動を始めて、他の壁マスを通らずに 壁マス} w \text{ に移動する経路数}\]

\[h(w,c)\coloneqq \text{壁マス }w \text{ から移動を始めて、他の壁マスを通ってもよいので} (R,c) \text{ に移動する経路数}\]

と定めると、障害物のある場合について、\(f_R\) は

\[f_L(X)(1+X)^{R-L}-\sum_{w\in W_{(L,R)}}\sum_{c}b_{w}h(w,c)X^c\]

の、\((R,c)\in W_{[R,R]}\) について \(X^c\) の係数を \(0\) とした多項式となります。(注: 計算時に \(W_{(L,R]}\) でなく \(W_{(L,R)}\) としてから最後の処理を行う理由は後程わかります。元の問題設定 では \((L,R]\) としてもよいです。)

\(h\) は簡単な二項係数で表されるため、\(b\) の求め方を考えます。これは公式解説で触れられているEDPC-Yを用いることで \(O(|W_{(L,R)}|^2+|W_{(L,R)}|(R-L)+|W_{[R,R]}|)\) で解くことができます。(注: \(f_L\) が計算できていることを利用して、 壁 \(w\) に至るまでの経路を \((0,0)\to(L,*)\to w\) と分解します。その際に考慮すべき始点 \((L,*)\) は壁 \(w\) に到達しうる \(O(R-L)\) 個のみで良いです。)

よって、\(f_L\) が既知のもとで \(f_R\) を \(O(|W_{(L,R)}|^2+|W_{(L,R)}|(R-L)+|W_{[R,R]}|+N\log{N})\) 時間で計算できます。

後は \([0,2N-2]\) を適切に区間に分割して、\(f\) を順に計算していけばよいです。

整数 \(B\) を定めて、区間は以下を満たすように分割します。(注: \(2\)つ目の条件を「\(|W_{(L,R]}|\) は高々 \(B\)」とするとそのような分割が存在しない場合があります。これが先ほど境界を別処理した理由です。)

• 区間の長さは高々 \(B\)
• 各区間\([L,R]\)について、\(|W_{(L,R)}|\) は高々 \(B\)
• そのような分割で分割の個数は最小

すると、区間の個数は高々 \(O(\frac{N+M}{B})\) となり、全体の計算量は \(O\left(\frac{N+M}{B}\left(B^2+N\log{N}\right)+M\right)\) です。\(B=\sqrt{N\log{N}}\) とすると、\(O((N+M)\sqrt{N\log{N}})\) です。