题目大意

给定一个二分图，已知这个二分图的完备匹配个数是奇数，询问删除每条边后完备匹配个数的奇偶。

$n\leq2000,m\leq5\times10^5$ 。

题解

线性代数苦手者。

令二分图的邻接矩阵为 $A$ ，二分图的完备匹配个数可以列式 $\sum_p\prod_{i=1}^nA_{i,p_i}$ 。由于题目只考虑奇偶，所以可以看作是在模 2 的背景下，此时邻接矩阵的行列式 $|A|=\sum_p(-1)^k\prod_{i=1}^nA_{i,p_i}=\sum_p\prod_{i=1}^nA_{i,p_i}$ 。我们便知道了 $|A|$ 就是二分图的完备匹配个数，为奇数。

考虑删除每条边的情况，只需要知道钦定该边存在的排列数奇偶性即可。它正好与余子式的意义相同——删去该行该列后矩阵的行列式。对于求解余子式有伴随矩阵的定义式

$$A^*_{i,j}=(-1)^{i+j}M_{j,i} $$

在模 2 意义下等价于

$$A^*_{i,j}=M_{j,i} $$

而求伴随矩阵又有性质

$$A^*=|A|A^{-1} $$

已知 $|A|$ 为奇数且在模 2 意义下所以等价于

$$A^*=A^{-1} $$

用 bitset 优化矩阵求逆即可，时间复杂度 $\mathcal{O}\left(\frac{n^3}{\omega}\right)$ 。

代码

const int N = 2010, M = 5e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	int u[M], v[M];
   	bitset<N << 1> a[N];
	int main () {
		n = Read(), m = Read();
		for (int i = 1; i <= m; i++) {
			u[i] = Read(), v[i] = Read();
			a[u[i]][v[i]] = 1;
		}
		for (int i = 1; i <= n; i++) a[i][i + n] = 1;
		for (int i = 1; i <= n; i++) {
			int mxi = i;
			for (int j = i + 1; j <= n; j++)
				if (a[j][i]) mxi = j;
			swap(a[i], a[mxi]);
			for (int j = 1; j <= n; j++)
				if (a[j][i] && j != i) a[j] ^= a[i];
		}
		for (int i = 1; i <= m; i++) puts(a[v[i]][n + u[i]]? "NO": "YES");
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}