生平罕见，竟会有如此思维难度如此高的题

这道题很难很难，非常难，但是题目很简短，代码也很简短，一道递推。

题目大意：对于一个 $4n$ 的图求哈密顿回路。

话不多说，开始推。

设 $f[i]$ 为前 $i$ 列中，第 $i$ 列的第一个格子到第二个格子的哈密度路的条数。(显然， $f[n]$ 就为答案)

设 $g[i]$ 为前 $i$ 列中，第 $i$ 列的第一个格子到第四个格子的哈密顿路的条数。

显然， $f[i]=f[i-1]+g[i-1]$

证明：

第 $i$ 列一二号格子的只能由两种方式得到：

这种情况为 $f[i-1]$ 。

这种情况为 $g[i-1]$ 。

这里不能从 $i-1$ 列的第三个格子直接，到第 $i$ 列，这样最终会走不到第 $i-1$ 列的第四个格子，不能形成哈密顿路。

下面介绍 $g[i]$ 的递推方法：

分四种情况进行讨论： $g[i]=g_1[i]+g_2[i]+g_3[i]+g_4[i]$

这种情况为 $g_1[i]$ ，由第 $i-1$ 列的情况可知， $g_1[i]=f[i-1]$ 。

这种情况为 $g_2[i]$ ,同理，可得 $g_2[i]=f[i-1]$ 。(就是把 $g_1[i]$ 的情况倒过来)。

这种情况为 $g_3[i]$ ,观察第 $i-2$ 列可知， $g_3[i]=g[i-2]$ .

这种情况为 $g_4[i]$ 。
又要分以下三种情况讨论：

这种情况通过观察第 $i-2$ 列，可知 $g_4[i]=f[i-2]$ 。

这种情况就是 $(1)$ 情况倒过来，故此时 $g_4[i]=f[i-2]$ 。

这种情况等同于这种情况：

就是将这种情况向前多增加了一列，故此时 $g_4[i]=g_4[i-1]$ 。

所以总共来说，

$g_4[i]=g_4[i-1]+f[i-2]×2=g[i-1]-g_1[i-1]-g_2[i-1]-g_3[i-1]+f[i-2]×2=g[i-1]-g[i-3]$

所以，

$g[i]=g_1[i]+g_2[i]+g_3[i]+g_4[i]=f[i-1]×2+g[i-1]+g[i-2]-g[i-3]$

在联立最初的结论 $f[i]=f[i-1]+g[i-1]$ ，可以得到最终的结论：

$f[i]=2×f[i-1]+2×[i-2]-2×f[i-3]+f[i-4]$ 。

初始化为：

$f[1]=0,f[2]=2,f[3]=4,f[4]=12$ 。

最后记得这道题还要用高精度，否则会爆。