【2017 BSUIR Semifinal D】Friends rescue 题解

题目大意

  有一个池塘，中间有 $n$n 行 $n+1$n+1 列的石头阵。
  连边只能连相邻的格子，相邻定义为四连通。
  现在左边第一列石头已经跟左边大陆 $L$L 相连，右边最后一列石头已经跟右边大陆 $R$R 相连。问剩下的有多少种连边方式，使得 $L$L 与 $R$R 连通。

  $n \leq 42$n≤42

$\\$
$\\$
$\\$

题解

  观察能力是真nmd缺啊。。。

  看这个图

  绿色边不影响连通性，先不考虑。
  我们要连的是红色的边，考虑把这幅图的对偶图做出来（蓝边），如果某一条红边没有连上，那么就把对应的蓝边连上。
  于是就会发现，每一种连边方案，要么 $LR$LR 连通，要么 $UD$UD 连通。
  进而发现，红边的规模跟蓝边的规模是完全一样的，也就是说，任意一种 $LR$LR 连通的方案，都可以翻转一下，成为一种 $UD$UD 连通的方案，反之亦然。
  所以 $LR$LR 连通的方案数等于 $UD$UD 连通的方案数。
  所以 $LR$LR 连通的方案数等于（红边的）总方案数除以 $2$2，再乘上绿边的方案数。