2022/4/5 21:36 MRI 聊天记录

· · 个人记录

题意：给定 n+m 个点的二分图，求其完美匹配个数 \bmod \ 2 的值。n,m \leq 10^3。

不妨设 n\leq m，写成矩阵形式。记答案为 f(A)。

首先考虑一个简单结论。记 A' 为 A 消元后的结果，f(A)=f(A')。

证明这个结论，我们考虑单独的两行。对应到原图上，如果存在边 p_1 \to p_2,p_1 \to q_2,q_1 \to p_2,q_1 \to q_2，可以直接删掉这四条边（因为可以交换匹配，系数为 2）；这样删去后两行可能还余下两个 1，对应到原图就是两个点需要同时匹配一个点，不合法所以系数为 0。

于是对 A 消元，得到 A' = [I_{n \times n} \mid B_{n \times (m-n)}]。意义是我们先假设左边 n 个点可以匹配右边 n 个点，然后右边剩下 m-n 个点去抢占之前匹配的 n 个点。我们现在要做的是算出 B 所有子方阵的行列式值 \bmod\ 2 之和（相当于枚举抢占的子集，没被抢占的会被之前一一对应的用走）。注意到在 \bmod \ 2 意义下可以把和变成平方的和，我们构造矩阵：

M=\left[ \begin{matrix} I_{(m-n)\times(m-n)} & B_{(m-n) \times n}^T \\ B_{n\times (m-n)} & I_{n\times n} \end{matrix} \right] 因为行列式是 $01$ 的，所以可以 `bitset` 优化消元。 --- 根据 Binet-Cauthy 定理，答案等价于 $\det(AA^T)$。根据定理显然。