如何在 n^3 内计算网格图完美匹配计数取模大质数
Aleph1022
·
·
个人记录
Petrozavodsk Winter 2009. Day 7: Ural SU Contest. Aztec Treasure
简要题意.
给定 n\times m 的网格图，求完美匹配个数模 10^9+7。
假设 n,m 同阶。
二分图完美匹配计数是计算积和式，考虑给竖边乘 i，就变成一个 nm/2 的方阵的行列式求值。
接下来考虑优化消元，考虑让第 (i,j) 行只剩 (1,1),(1,2),\dots,(1,m) 和 (i+1,j) 这些位置，容易做到 O(n^3)。
这个做法是比较 NOIP 的，但是我们可以做得更有趣一些。
以下参考自唐老师的文章和这里的 J。
考虑正常做 FKT，令竖向边全部向下，奇数行的横向边向右，偶数行向左，这样归约到求 Pfaffian。
$$
\begin{bmatrix}
& 1 & & 1 \\
-1 & & 1 & & -1 \\
& -1 & & & & 1 \\
-1 & & & & 1 & & 1 \\
& 1 & & -1 & & 1 & & -1 \\
& & -1 & & -1 & & & & 1 \\
& & & −1 & & & & 1 & & 1 \\
& & & & 1 & & −1 & & 1 & & −1 \\
& & & & & −1 & & −1 & & & & 1 \\
& & & & & & −1 & & & & 1 \\
& & & & & & & 1 & & −1 & & 1 \\
& & & & & & & & −1 & & −1
\end{bmatrix}
$$
取 $U = \left\{[i+1=j]-[i=j+1]\right\}_{i,j=1}^n$，$V = \left\{[i=j](-1)^{i-1}\right\}_{i,j=1}^n$，可以发现该矩阵分块后可得
$$
\begin{bmatrix}
U & V \\
-V & U & V \\
& -V & U & V \\
& & -V & U
\end{bmatrix}
$$
可以归纳证明，该矩阵的行列式和 Pf 等于 $n$ 阶方阵 $(-1)^{nm/2} F_m$ 的对应值。其中
$$
F_0 = I, F_1 = U, F_m = U \cdot F_{m-1} - F_{m-2} \quad (k\ge 2)
$$
注意到 $U$ 是特殊的，所以这部分可以 $O(n^3)$ 解决。
事实上，该递推也可以描述为 $2n$ 阶矩阵的高次幂，且其特征多项式也可以递推得到，所以大概可以在 $n,m$ 不同阶的时候做到更好。
接下来有另外一个做法。
首先多米诺骨牌覆盖计数有一个著名公式
$$
\prod_{j=1}^m \prod_{k=1}^n \left(4\cos^2\frac{j\pi}{m+1} + 4\cos^2\frac{k\pi}{n+1}\right)^{1/4}
$$
设 $r_n(k) = 2\cos\left(\frac{k\pi}{n+1}\right)$，原式可以化为
$$
\begin{aligned}
&= \prod_{j=1}^m \prod_{k=1}^n \left(r_m^2(j)-i^2r_n(k)\right)^{1/4} \\
&= \prod_{j=1}^m \prod_{k=1}^n \left(r_m(j)-ir_n(k)\right)^{1/4}\left(r_m(j)+ir_n(k)\right)^{1/4}
\end{aligned}
$$
设 $F_m(x) = \prod_{k=1}^n (x-r_n(k))$，注意到 $r_m(j)+r_m(m-j+1)=0$，原式可以继续化为
$$
\begin{aligned}
&= \prod_{j=1}^m F^{1/4}(i r_m(j))^{1/4} F^{1/4}(-i r_m(j)) \\
&= \prod_{j=1}^m F^{1/4}(i r_m(j))^{1/4} F^{1/4}(i r_m(m-j+1)) \\
&= \prod_{j=1}^m F^{1/2}(i r_m(j)) \\
\end{aligned}
$$
事实上，这个 $F(x) = U_n(x/2)$，其中 $U_n(x)$ 是第二类切比雪夫多项式。
关于切比雪夫多项式，有一个结论
$$
U_n(x) = \det(2xI + A), A = \{[|i-j|=1]\}_{i,j=1}^n
$$
因此
$$
\prod_{j=1}^m F(i r_m(j)) = \prod_{j=1}^m \det(i r_m(j)I + A/2) = (-i)^{nm} \det\left(\prod_{j=1}^m(iA/2 - r_m(j)I)\right)
$$
这里又出现了一个 $U_m(iA/2)$，因此我们考虑如何求这个。我们有
$$
U_0(x)=1, U_1(x)=2x, U_m(x) = 2xU_{m-1}(x) - U_{m-2}(x) \quad (m\ge 2)
$$
从而我们就得到了和上一种做法十分相似的结论。