Day 116-Q1 | FKT算法（Pfaffian Orientation）

問題

$H \times W$ のマス目からなるグリッドがある。すべてのマスをちょうど1つのドミノ（$1\times2$または$2\times1$の長方形）で敷き詰める方法の総数を求めよ。

入力形式

H W

制約

$1 \le H, W \le 8$

$H \times W \le 64$

入出力例

入力例1

2 2

出力例1

入力例2

2 4

出力例2

$2\times n$ の敷き詰め数はフィボナッチ数列に一致する（$2\times4=5$）。

概念図: Kasteleyn orientation（グリッドの向き付け規則）

ヒント（段階的開示）

ヒント1: 方向性

一般のグラフの完全マッチングの数え上げは、パーマネント（permanent）の計算に対応し#P困難であることが知られている。しかしグリッドグラフは平面的（planar）である。「行列式（determinant）は多項式時間で計算できるのに、パーマネントはできない」という違いに着目し、マッチングの数え上げを行列式計算に帰着させる方法を考える。

ヒント2: アプローチ

各辺に向きと符号を適切に割り当てた「歪対称行列」（skew-symmetric matrix、$K^T=-K$）を作ると、その行列式の平方根（Pfaffian）が完全マッチングの符号付き総和に一致するように仕込める。この向き付けを Pfaffian orientation と呼ぶ（FKT algorithm の核心）。グリッドグラフでは、水平な辺はすべて同じ符号、垂直な辺は列ごとに符号を交互に反転させる、という単純な規則（Kasteleynの構成）だけでこの条件を満たせることが知られている。

ヒント3: 誘導（コード骨格）

# K[u][v] = +sign, K[v][u] = -sign の歪対称行列を作る
# 水平辺 (i,j)-(i,j+1): sign = 1 で統一
# 垂直辺 (i,j)-(i+1,j): sign = 1 if j % 2 == 0 else -1
# あとは det(K) を計算してその平方根を取れば答え
# （Pfaffianの2乗が行列式に一致するため、detは必ず非負の完全平方数になる）

模範解答 (Python)

import sys
import math


def bareiss_det(mat):
    """整数行列の行列式を、除算を分数化せずに厳密に計算する（Bareissのアルゴリズム）。"""
    n = len(mat)
    if n == 0:
        return 1
    M = [row[:] for row in mat]
    sign = 1
    prev = 1
    for k in range(n - 1):
        if M[k][k] == 0:
            piv = -1
            for i in range(k + 1, n):
                if M[i][k] != 0:
                    piv = i
                    break
            if piv == -1:
                return 0
            M[k], M[piv] = M[piv], M[k]
            sign = -sign
        pivot = M[k][k]
        for i in range(k + 1, n):
            mik = M[i][k]
            row_i = M[i]
            row_k = M[k]
            for j in range(k + 1, n):
                row_i[j] = (row_i[j] * pivot - mik * row_k[j]) // prev
        prev = pivot
    return sign * M[n - 1][n - 1]


def solve():
    H, W = map(int, sys.stdin.read().split())
    N = H * W
    if N % 2 == 1:
        print(0)
        return

    def idx(i, j):
        return i * W + j

    K = [[0] * N for _ in range(N)]
    for i in range(H):
        for j in range(W):
            u = idx(i, j)
            if j + 1 < W:
                v = idx(i, j + 1)
                K[u][v] += 1
                K[v][u] -= 1
            if i + 1 < H:
                v = idx(i + 1, j)
                sign = 1 if j % 2 == 0 else -1
                K[u][v] += sign
                K[v][u] -= sign

    det = bareiss_det(K)
    ans = math.isqrt(abs(det))
    print(ans)


solve()

計算量: 行列サイズ $N=HW$、Bareiss法で $O(N^3)$。$H,W\le8$ なら $N\le64$ なので瞬時に終わる。$2\times2\to2$、$2\times4\to5$、$4\times4\to36$、$4\times6\to281$（独立手法の profile DP でクロスチェック済み）と一致することを確認済み。

Step-by-Step 解説

1歪対称行列 $K$ の構築（Kasteleyn orientation）
各マスを頂点とし隣接マス間に辺を張る。水平辺は常に符号$+1$、垂直辺は列$j$の偶奇で符号を反転させる。この単純な規則だけでグリッドグラフに対する正しいPfaffian orientationになる。

2Bareiss法による整数行列式の厳密計算
浮動小数点だと丸め誤差で答えが崩れる。Bareissのアルゴリズムは途中の除算が必ず割り切れることを保証しながら整数のまま行列式を計算する分数フリーのガウス消去法。

3Pfaffianと行列式の関係
歪対称行列$K$について $\det(K)=\mathrm{Pf}(K)^2$ が成り立つ。Pfaffian orientationのもとでは $\mathrm{Pf}(K)$ が完全マッチングの総数に一致するため、$\det(K)$ の非負整数平方根を取れば答えが得られる。

4$H\times W$が奇数のときの早期終了
マス目の総数が奇数なら隙間なく埋めることはできないため、行列式を計算するまでもなく$0$を出力する。

5計算量の確認
$O(N^3)$、$N\le64$なので余裕を持って高速に動作する。より大きなグリッドを扱う場合はmod素数での行列式計算への拡張が必要になる。

よくあるミス

ミス	原因	正しい書き方
符号なしのパーマネントとして数え上げようとし、計算量が破綻する	一般グラフのマッチング数え上げが#P困難であることを忘れる	Pfaffian orientationにより行列式（多項式時間で計算可能）に帰着させる
垂直辺の符号を全て同じにしてしまう	列ごとの交互反転（Kasteleyn条件）を見落とす	列インデックス$j$の偶奇で`sign`を反転させる
Bareiss法の除算を浮動小数点で行い誤差が出る	通常のガウス消去法と混同する	常に整数除算`//`を使い、1つ前のpivotで必ず割り切れることを利用する
行列式が完全平方数になることを確認せず実装ミスに気づけない	Pfaffianの数学的性質を検証していない	実装が正しければ`det`は常に非負の完全平方数になる。ずれた場合は向き付けのバグを疑う

次のステップ

発展: グリッド以外の一般平面グラフに対するPfaffian orientationの構成法（T-join法）を調べる
発展: mod素数でのPfaffian計算に拡張し、より大きいグリッドサイズに対応させる

自己評価

完全理解おおむね理解要復習

Day 116-Q1 — FKT算法（Pfaffian Orientation・グリッドグラフの完全マッチング数え上げ）

問題