「Codeforces 736D」Symmetric and Transitive 题解

题目

题意

左右各 \(n\) 个点，\(m\) 条边的二分图，满足完美匹配数为奇数个，问分别去掉每一条边后，完美匹配数是否仍为奇数个

\(n\le2000\)，\(m\le5\times10^5\)

分析

首先发现完美匹配数为 \(\sum\limits_{\sigma\in S_n}\prod\limits_{i=1}^n\left[M_{i,\sigma(i)}=1\right]\)，其中 \(M\) 为邻接矩阵，\(S_n\) 为所有 \(1\sim n\) 的置换构成的集合

由于是 \(\bmod2\) 意义下的，且 \(-1\equiv1\pmod2\) 故有 \(Ans\equiv\sum\limits_{\sigma\in S_n}\operatorname{sgn}(\sigma)\prod\limits_{i=1}^n\left[M_{i,\sigma(i)}=1\right]=\det(M)\pmod2\)

考虑容斥，去掉一条边的完美匹配数为奇数等价于包含一条边的完美匹配数为偶数，必须包含一条边即为删掉一行一列，于是等价于它的余子式为偶数，同样的，由于 \((-1)^{i+j}\) 不影响答案直接求代数余子式即可，又有矩阵 \(M\) 在 \(i\) 行 \(j\) 列的代数余子式等于伴随矩阵 \(M^{\*}\) 的 \(j\) 行 \(i\) 列，于是可以求伴随矩阵 \(M^{\*}=\det(M)M^{-1}\) 直接高斯消元就好了，\(\det(M)\) 一定为奇数

注意到运算在 \(\bmod2\) 意义下进行，加减和异或运算等价，直接使用 bitset 进行优化即可，复杂度 \(\operatorname{O}(\frac{n^3}{\omega})\)

代码

constexpr int N = 2001;
constexpr int S = 4001;
constexpr int M = 500001;

void Gauss(int n);

std::bitset<S> a[N];
int u[M], v[M];
int n, m;

int main() {
  read(n), read(m);
  for (int i = 1; i <= m; ++i) {
    read(u[i]), read(v[i]);
    a[u[i]][v[i]] = true;
  }
  for (int i = 1; i <= n; ++i) {
    a[i][i + n] = true;
  }
  Gauss(n);
  for (int i = 1; i <= m; ++i) {
    if (a[v[i]][u[i] + n]) {
      puts("NO");
    } else {
      puts("YES");
    }
  }
  return 0;
}

void Gauss(int n) {
  for (int i = 1; i <= n; ++i) {
    int now = 0;
    for (int j = i; j <= n; ++j) {
      if (a[j][i]) {
        now = j;
      }
    }
    if (now != i) {
      std::swap(a[i], a[now]);
    }
    for (int j = 1; j <= n; ++j) {
      if (i != j && a[j][i]) {
        a[j] ^= a[i];
      }
    }
  }
}