行列式的一些妙用

我们知道 \(\det(A)=\sum\limits_{p}(-1)^{\sigma(p)}\prod\limits_{i}A_{i,p_i}\)，这是行列式的定义。

我们定义 \(A\) 积和式为 \(\sum\limits_{p}\prod\limits_{i}A_{i,p_i}\)。

积和式的计算是 NP 的。但是有的时候我们可以用行列式来完成一些积和式可以完成的东西。

比如最简单的，给定一个两边分别有 \(n\) 个点的二分图，问是否存在完美匹配。算邻接矩阵 \(G_{i,j}=[(L_i,R_j)\in E]\) 积和式的值就可以得到完美匹配的数量。但是由于是判定性问题，我们可以考虑用行列式做，做法如下：

将每条边附一条 \([0,P)\) 范围内的随机边权，\(G\) 是带权邻接矩阵。那么我们只需要判断行列式的值是否为 \(0\) 就可以了。考虑感受这个做法的正确性：首先如果不存在完美匹配，算出来的行列式肯定是 \(0\)。这个做法本质上来说相当于是对每个完美匹配赋予了一个随机权值，算出来的值就是所有完美匹配的权值和。故由于随机化，大部分情况的判断是正确的。概率证明可以看 Schwartz–Zippel 引理。

但是你会说这个东西我直接匈牙利就算完了呀。确实，不过因为匈牙利在这一方面并不是万能的。考虑下面一个问题：

还是上述二分图，但是边有 \([0,2^k)\) 的边权。对于所有 \(x\in[0,2^k)\) 求是否有完美匹配使得其边权按位与和是 \(x\)。

用容斥的方法肯定就是算边权按位与和为 \(k\) 的超集的方案数，再减去超集的答案数。这下匈牙利就无能为力了。而由于行列式方法相当于是对每个完美匹配赋予一个权值，所以这道题还是能够把行列式的值当作前面提到的方案数来计算。在时间复杂度 \(\mathcal O(n^32^k)\) 内解决了这个问题。