[AtCoder] ABC 183 E – Queen on Grid

問題

方針

まず、壁がない場合を考えます。

\( d(i, j) \) をマス \( (1, 1)\) から マス \( (i, j) \) への移動方法の数とします。\( d(i, j) \) は、\( n = \min (i, j) \) として、

\begin{eqnarray}
d(i, j) &=& d(i – 1, i) + d(i – 2, i) + \cdots + d(1, i)\\
&+& d(i, j – 1) + d(i, j – 2) + \cdots + d(j, 1) \\
&+& d(i – 1,  i – 1) + d(i – 2, i – 2) + \cdots + d(i – n, j – n) \\
&=& \sum_{k = 1} ^{i – 1} d(i – k, j) + \sum_{k = 1} ^{j- 1} d(i , j – k) + \sum_{k = 1} ^{n – 1} d(i – k, j – k)
\end{eqnarray}

となります。また、\( d(1, 1) = 1\) です。ここで、\( a(i, j), b(i, j), c(i, j) \) を

\begin{eqnarray}
a(i, j) &=& \sum_{k = 1} ^{i – 1} d(i – k, j) \\
b(i, j) &=& \sum_{k = 1} ^{j – 1} d(i, j – k) \\
c(i, j) &=& \sum_{k = 1} ^{n – 1} d(i – k, j – k) \\
\end{eqnarray}

とすると、

\[ d(i, j) = a(i, j) + b(i, j) + c(i, j)\]

となります。また、\( a(i, j), b(i, j), c(i, j) \) は

\begin{eqnarray}
a(i, j) &=& a(i – 1, j) + d(i – 1, j)\\
b(i, j) &=& b(i, j – 1) + d(i, j – 1)\\
c(i, j) &=& c(i – 1, j – 1) + d(i – 1, j – 1)
\end{eqnarray}

となるので、累積和として高速に計算できます。壁を考慮するときは、マス \( (i -1  , j) \) 、マス \( (i, j – 1) \) 、マス \( (i – 1, j – 1)\) からマス \( (i, j)\) へと移動することができるかどうかを調べます。

コード