FKT Algorithm

题目描述(Domino Tiling)

现在有一个 $m\times n$ 大小的正方形格子阵列(保证 $mn$ 为偶数),如果用 $1\times 2$ 的瓷砖去铺盖,问有多少种覆盖的方法?

Solution:

假设 n=2

可以设结果为关于 $m$ 的函数 $f(m)$.
若第一块瓷砖是横着放的,则回归到 $f(m-1)$
若是竖着放的,可以想到必然是两列都是竖着放的,这样回归到 $f(m-2)$
所以有 $f(m)=f(m-1)+f(m-2)$ 转化为 Fibonacci 数列问题

DP?

可以构造一个状态压缩的DP,来求解该问题的较小规模结果
详见瓷砖覆盖(状压DP)

匹配数:

事实上,对该格点整列进行国际象棋棋盘一样的黑白间隔染色,把每个方格抽象成顶点,在上下左右相邻的方格之间加入一条边,这样得到一个无向图
显然,黑色的顶点与白色的顶点构成二分图的两个部
用瓷砖覆盖变成求该二分图的完美匹配
覆盖的方法种数就是求解该二分图的匹配数了
对于一般的二分图,求解匹配数就是计算其的二分图邻接表($ a_\{m,n\}$ 表示第一个部中第 $m$ 个顶点是否与第二个部中第 $n$ 个顶点有连边)的积和式(Permanent),积和式定义为:

其中 $S_n$ 为 $\{1,2,\cdots,n\}$ 的全排列
积和式的定义看上去与行列式相像,就是行列式的求和项中去掉了关于奇偶排列的符号项
但积和式的计算比行列式困难的多,行列式有 $O(n^3)$ 的 Gauss 消元方法,而积和式只能逐项计算,复杂度 $O(n!)$
但如果我们的二分图满足更强的一些条件,就可以针对性地进行优化
当二分图满足是可平面图的条件时,其匹配数的计算有多项式时间的算法(FKT Algorithm)

Pfaffian:

直接写出二分图的邻接矩阵(注意这里不再是原先的一部-二部矩阵了,而是完全的(0,1)-邻接矩阵,这意味着矩阵会形如 $\begin{matrix}\boldsymbol O&\boldsymbol A\\\boldsymbol A^T&\boldsymbol O\end{matrix}$),可以这样计算匹配数:

(矩阵阶数为 $2n$ ,注意前面的系数 $\frac 1{2^nn!}$ 来自于重复计数)
而邻接矩阵的普法夫型如下:

显然,如果我们为原先的无向图定向,得到新的(-1,0,1)-邻接矩阵 $A’$ ,使得计数项内的 $sgn(\sigma)$ 与其后的连乘式符号相同,则有普法夫型的绝对值等于完美匹配数 $|pf(A’)|=\text{PerfectMatch(A)}$
考虑到 $A$ 为二分图的邻接矩阵,每一个连乘项若不是 $0$ 那么 $(\sigma(1),\sigma(2)),(\sigma(3),\sigma(4)),\cdots,(\sigma(2n-1),\sigma(2n))$ 每一项都不能是 $0$ ,即它们构成一个完美匹配
由于如果统一符号,则计算结果取绝对值即可,只需考虑:
从任意一个圈上一点出发,绕着该圈走一遍,经过的逆向边的数目(乘以-1的次数)与经过的正向边的数目(乘以1的次数)都是奇数
如果能够保证以上条件,排列 $\sigma$ 的逆序数就恰好和连乘的最终符号保持一致
而对于可平面二分图,由于它是二分的,则所有的圈必然为偶圈,因此一定可以将该偶圈剖分为奇数条正向和奇数条反向边
同时由于可平面性,该图的全部圈可由一组基本圈组生成,不难验证上述的双奇数性质经过可平面的圈拼接是可遗传的(对于两个拼起来的圈而言,它们组成的新的圈是成对地去除原先各自的同向边)
同时,反对称矩阵的普法夫型具有以下性质

有向图的邻接矩阵自然是反对称的,由此可以解得

而求解行列式已经有了多项式时间的高斯消元算法
这样我们只需要在多项式时间内找到一个这样的定向:

  1. 计算图 $G$ 的平面嵌入
  2. 计算 $G$ 的一棵生成树 $T_1$
  3. 对 $T_1$ 上的每一条边给予任意的定向(同时在 $G$ 上做标记,一般地可以取从树心向外的方向)
  4. 利用平面嵌入构造图 $G$ 的对偶图(面-点,边-边转换)的空图(只有顶点,边一会再一条条地加入) $T_2$
  5. 若 $T_2$ 中两个顶点对应到 $G$ 中的两个面相邻,且邻边不在 $T_1$ 中,则在 $T_2$ 中将这两个顶点相连(这样最后得到的 $T_2$ 也是树,因为若不是树,说明 $T_2$ 中存在圈围起来了原图 $G$ 中的一些点,这样势必会破坏 $T_1$ 的连通性)
  6. 对于 $T_2$ 中的叶子,将它关联的唯一的那条边对应到原图 $G$ 中的边定向,使得它所在的一个圈里的顺时针方向的边的数目保持为奇数,然后在 $T_2$ 中删除这个叶子
    以上各步骤均为多项式复杂度的,因此我们在多项式时间内求解出了可平面二分图的完美匹配数

回到原题

那么原先这个铺砖的题目里,我们抽象出来的图显然是可平面的(因为本来就是从平面整列里得到的)
可以很轻松地手工找到一个定向,如下:
Directinoal
也就是对竖着的边全部向下定向,横着的边S形定向
但计算该图的过程还是十分困难,细节就不在这里写了
下面给出最终的答案

Result:

*This result also works when $mn$ is odd, by giving the zero outcome.
*There are many interesting result for other shape, like, for Aztec diamond , the result is $2^{\frac{n(n+1)}{2}}$