考察

各マスについて、ちょうど1回だけカウントする方法を考えます。「最後にそのマスを踏む瞬間」を考えます。その瞬間が \(N-k\) 歩目のランダムウォーク後とすると、「残りの \(k\) 歩でそのマスに戻ってこない」ということが「最後にそのマスを踏んだ」ということと同値になります。

頑張って数える

「残りの \(k\) 歩でそのマスに戻ってこない」場合の数はどのようになるでしょうか？

\(G(m)\) \((m\ge 1)\) を、 \(m\) 歩目で同じマスに初めて戻ってくる場合の数とします。

そうすると、「残りの \(k\) 歩でそのマスに戻ってこない」場合の数は

\[\sum_{i=1}^{k} G(i) 4^{k-i}\]

となります。今、最初の \(N-k\) 歩でどんなランダムウォークをしてもこれは同じ式です。よって答えは

\[ \begin{aligned} & \sum_{k=0}^N 4^{N-k}\sum_{i=1}^{k} G(i) 4^{k-i}\\ = & \sum_{k=0}^N \sum_{i=1}^{k} G(i) 4^{N-i} \end{aligned} \]

よって、 \(G(1),G(2),\cdots, G(N)\) が求まれば答えが \(O(N^2)\) で求まります。

\(G\) を求めるために、補助的に \(F(m)\) を、 \(m\) 歩目で同じマスに（初めてとは限らず）戻ってくる場合の数とします。

そうすると、 \(G\) と \(F\) は次の関係があります。これはいわゆる除原理という式です。

\[G(m) = F(m) - \sum_{i=1}^{m-1} G(i) \times F(m-i)\]

よって、 \(F(0), F(1), \cdots, F(N)\) が分かれば、 \(O(N^2)\) で \(G(0), G(1) \cdots, G(N)\) が求まります。

そして、 \(F\) は実際に求められます。

\(F\)

\(m\) 歩目で同じマスに戻ってくるとき、 \(x\) 座標の正と負、 \(y\) 座標の正と負の回数がそれぞれ同じになる必要があります。

たとえば指数型形式的冪級数を用いると、

\[F(m) = m! [x^m] \left(\sum_{n\ge 0} \binom{2n}{n}\frac{x^{2n}}{(2n)!}\right)^2\]

となります。これは \(O(N^2)\) 時間で計算できます。

ただし、 \(M\) が素数とは限らないことに注意が必要です。このために、階乗の逆元を扱うのが不便です。代わりに、 \(\binom{n}{k}\) をパスカルの三角形のように \(O(N^2)\) 時間で前計算をすれば、

\[F(m) = \sum_{i=0}^m \binom{m}{i} \left([x^i] \sum_{n\ge 0} \binom{2n}{n} x^{2n}\right)\left([x^{m-i}] \sum_{n\ge 0} \binom{2n}{n} x^{2n}\right)\]

で求められます。

以上から合計 \(O(N^2)\) 時間・空間でこの問題が解けました。なお、特に \(M\) が素数だと形式的冪級数のテクニックで \(O(N \log^2 N)\) で解けます。