CF736D Permutations

Posted on | Views:

利用伴随矩阵求代数余子式.

给定一张两侧各 $n$ 个点,共 $m$ 条边的二分图,保证其完美匹配个数为奇数

对于二分图的每一条边,询问将这条边删去后,剩下的二分图的完美匹配数是否仍为奇数.

$n\le 2000,m\le \min(n^2,5\times 10^5)$ .

定义一个矩阵 $A$ , 若左侧的 $i$ 与右侧的 $j$ 有边,则 $A_{i,j}=1$ ,否则 $A_{i,j}=0$ .

那么这张二分图完美匹配数为奇数等价于 $\sum_p \prod_{i=1}^n a_{i,p_i}\equiv 1\pmod 2$ .

而 $-1$ 在模 $2$ 意义下也是 $1$ ,所以给每一项乘个 $-1$ 的 $p$ 的逆序对数次方,值不变,这个东西就是 $\det(A)$ .

即,这张二分图完美匹配数为奇数等价于 $\det(A)\equiv 1\pmod 2​$ .

现在要算去掉某条边后完美匹配数的奇偶性,容斥一下,变成算必须包含它的完美匹配数的奇偶性.

不难发现必须包含它的数目就是 $A_{i,j}$ 的余子式,可以乘上 $(-1)^{i+j}$ 变成代数余子式.

于是我们需要对 $A$ 的每个元素求出代数余子式.

保证了 $\det(A)\equiv 1\pmod 2$ ,求出 $A​$ 的伴随矩阵

$$
A^{*}=\det(A)A^{-1}
$$

即可求出 $A_{i,j}$ 的代数余子式 $(-1)^{i+j}M_{i,j}=A^{*}_{j,i}$ .

瓶颈在于求出 $A^{-1}$ ,而运算是在模 $2$ 意义下进行的,可以用 bitset 优化,时间复杂度 $O(\frac{n^3}{w})$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int N = 2e3 + 10, M = 5e5 + 10;
bitset<N> A[N], B[N];
int n, m, st[M], ed[M];
void Guass()
{
	for (int i = 0; i < n; ++i)
	{
		for (int j = i; j < n; ++j)
			if (A[j][i])
			{
				if (i != j)
				{
					swap(A[i], A[j]);
					swap(B[i], B[j]);
				}
				break;
			}
		for (int j = 0; j < n; ++j)
			if (i != j && A[j][i])
				A[j] ^= A[i], B[j] ^= B[i];
	}
}
int main()
{
	n = read(), m = read();
	for (int i = 0; i < m; ++i)
	{
		int u = read() - 1, v = read() - 1;
		A[u][v] = 1;
		st[i] = u, ed[i] = v;
	}
	for (int i = 0; i < n; ++i)
		B[i][i] = 1;
	Guass();
	for (int i = 0; i < m; ++i)
		if (B[ed[i]][st[i]])
			puts("NO");
		else
			puts("YES");
	return 0;
}