本来还有 $30$ 分给多项式的，但是阻碍了伟大的 hxf 的 AK 之路，考虑到 CCF 不会出多项式，所以去掉了这一部分。

正难则反，考虑去算有那几步是不会产生贡献的，若第 $i$ 步不会产生贡献，则说明之前已经走到过这里一次了。

枚举第 $i$ 步所在的格子在 $t$ 步之前已经来到过这里了，设 $f_i$ 表示从一个位置出发，走 $i$ 步又回来，期间不经过这个位置的方案数。限制中间不经过是为了防止算重，求出 $f$ 后，答案为 $\sum_{i=1}^n\sum_{t=1}^if_t4^{n-t}$，不难发现这个式子和 $i$ 无关，继续化简为 $\sum_{t=1}^nf_t4^{n-t}(n-t+1)$。

问题是如何求出 $f$，考虑单步容斥，先求出 $g_i$ 表示从一个位置出发，走 $i$ 步又回来的方案数，则有 $f_i=g_i-\sum_{j=1}^{i}f_jg_{i-j}$。

对于 $g_i$，可以枚举竖直方向走了多少步，水平方向走了多少步，组合起来，通过组合恒等式可以证明当 $i$ 为偶数时，$g_i=(C_{i}^{i/2})^2$。另外一个方法是旋转坐标系 $45$ 度，无论上下左右都相当于在竖直和水平上都选择一个方向走一个单位长度，也能直接得到这个结论。

直接计算即可，瓶颈在于求 $f$，实际上可以用多项式优化，但是不是很文明所以去掉了。朴素实现是 $O(n^2)$，多项式是 $O(n\log n)$，听说存在 $O(n)$ 的做法。