【GYM100959H】Random Walk

\(\texttt{Petrozavodsk Winter Training Camp 2016

Day 3 } \text{Random Walk}\)​

有一個無限大的二維平面，一開始你在 \((0,0)\) 上，你會走 \(N\) 步，每次在上下左右四個方向裡随機選擇一個後往那個方向上走一步。

求經過格子數量的期望，答案對 \(998244353\)​​​​​​ 取模。 （ \(N\le 5000\)​​​​​​ ，注意題面與原題略有不同）

為友善，将移動寫作向量的形式，整個移動過程就變成了 \(N\)​​​​​​​ 個向量組成的序列 \(A\)​​​​​ 。設 \(pre(A,i)=\sum_{j=1}^{i} A_j\)​​​​​ ，發現一個方案的經過格子數可以描述為

\[\sum\limits_{i=0}^{N}[\forall0\le j<i,pre(A,j)\not=pre(A,i) ]

\]

答案可以寫作

\[\frac{\sum_{|A|=N}\sum_{i=0}^{N}[\forall0\le j<i,pre(A,j)\not=pre(A,i) ]}{4^N}

或者等價地

\[\frac{\sum_{i=0}^{N}(4^N-\sum_{|A|=N}[\exist0\le j<i,pre(A,j)=pre(A,i) ])}{4^N}

進一步地，發現 \(A\)​​ 從第 \(i\)​​ 項開始對 \([\exist0\le j<i,pre(A,j)=pre(A,i)]\)​​​​ 沒有影響了。是以分子還可以寫作

\[\sum\limits_{i=0}^{N}(4^{N-i}\times(4^i-\sum\limits_{|A|=i}[\exist0\le j<i,pre(A,j)=pre(A,i) ]))

定義 \(f_i=4^i-\sum_{|A|=i}[\exist0\le j<i,pre(A,j)=pre(A,i) ]\)​​​​ ，嘗試在 \(O(n^2)\)​​​​ 的時間内計算出 \(f_i,i-0,1,\cdots,n\)​​​​ 。将 \(f_i\)​​​​ 改寫回 \(\sum_{|A|=i}[\forall0\le j<i,pre(A,j)\not=pre(A,i) ]\)​​​​​ ，​發現有遞推式

\[f_i=4^i-\sum\limits_{j=0}^{i-1}f_jg_{i-j}

其中 \(g_i\)​​​​ 表示長度為 \(i\)​​​​ 的和為 \((0,0)\)​​​​ 的序列的數量。這條式子的正确性可以考慮對每個滿足 \(\exist0\le j<i,pre,(A,j)=pre(A,i)\)​​​​ 的序列 \(A\)​​​​ ，找出它滿足和為 \(0\)​​​​​​ 的最大字尾，然後反過來作一個一一對應即可。

現在考慮計算 \(g_i\) ，顯然 \(i\) 為奇數時值為 \(0\) ；反之，向量 \((0,1)\) 和 \((0,-1)\)​ 必然成對出現，枚舉它們的數量則有

\[g_i=\sum\limits_{j=0}^{i/2} \frac{i!}{j!j!\frac{i-2j}{2}!\frac{i-2j}{2}!}

好像還是不太好算。為了可讀性，設 \(k=i/2\)​​​ ，則

\[\begin{aligned}

& \sum\limits_{j=0}^{k}\frac{(2k)!}{j!j!(k-j)!(k-j)!} \\

=& \frac{(2k)!}{k!k!}\sum\limits_{j=0}^{k}\frac{k!k!}{j!j!(k-j)!(k-j)!} \\

=& \binom{2k}{k}\boxed{\sum\limits_{j=0}^{k}\binom{k}{j}\binom{k}{k-j}}\text{ （範德蒙德卷積）} \\

=& \binom{2k}{k}\binom{2k}{k}

\end{aligned}