【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}