题目大意
有一个池塘，中间有 $n$ 行 $n+1$ 列的石头阵。
连边只能连相邻的格子，相邻定义为四连通。
现在左边第一列石头已经跟左边大陆 $L$ 相连，右边最后一列石头已经跟右边大陆 $R$ 相连。问剩下的有多少种连边方式，使得 $L$ 与 $R$ 连通。
$n \leq 42$
题解
观察能力是真nmd缺啊。。。
看这个图
绿色边不影响连通性，先不考虑。
我们要连的是红色的边，考虑把这幅图的对偶图做出来（蓝边），如果某一条红边没有连上，那么就把对应的蓝边连上。
于是就会发现，每一种连边方案，要么 $LR$ 连通，要么 $UD$ 连通。
进而发现，红边的规模跟蓝边的规模是完全一样的，也就是说，任意一种 $LR$ 连通的方案，都可以翻转一下，成为一种 $UD$ 连通的方案，反之亦然。
所以 $LR$ 连通的方案数等于 $UD$ 连通的方案数。
所以 $LR$ 连通的方案数等于（红边的）总方案数除以 $2$，再乘上绿边的方案数。