(False)faces | Cerc2009

题目链接

给定一个两边各有 \(n\) 个点的二分图,判断完美匹配的个数是否是 \(4\) 的倍数。

\(n \le 300\)

完美匹配的个数即积和式。

来自论文的算法:求积和式模 \(4\) 的余数。

积和式定义 \[ \text{perm }A = \sum_{p}A_{i,p_i} \]\(A\)\(01\) 矩阵时,有 \[ \text{prem} A = (-1)^n\sum_{x_i \in \{0,1\}}(-1)^{x1+x2+\cdots+x_n}\prod_{i=1}^n(Ax)_i \] 证明可以考虑容斥:枚举哪些行=列一定没有被选。

观察到式子中间有一个 \(\prod\) ,由于我们要求这个东西模 \(4\) 的余数,因此 \((Ax)_i\) 至多只能有一个位置模 \(2\)\(0\)

考虑 \((Ax)_i\) 每一项模 \(2\) 的余数,由于至多只能有一个 \(0\),因此可以枚举这个东西的取值,它只有 \(n+1\) 种。

对于每种取值,通过高斯消元解出满足条件的所有 \(x\),再将每一组 \(x\) 代入刚刚的式子中求出答案。

问题是,合法的 \(x\) 的个数可能很大,因为需要枚举自由元的取值。

对这个矩阵做一些变换。 \[ \begin{bmatrix} A_{1,1}&A_{1,2}&\cdots &A_{1,n}&v_1\\ A_{2,1}&A_{2,2}&\cdots &A_{2,n}&v_2\\ \vdots&&&&\vdots\\ A_{n,1}&A_{n,2}&\cdots &A_{n,n}&v_n\\ 0&0&\cdots&0&1 \end{bmatrix} \] 这个矩阵的积和式等于原矩阵的积和式。

随机选取 \(v\),则期望 \(O(1)\) 组解。

复杂度 \(O(n^4)\)

代码:

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
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back

using namespace std;
const int N = 305;
int T, n, as;
char s[N];
bitset <302> A[N], bas[N];
int x[N];
void dfs(int i) {
if(i > n) {
int mul = 1;
rep(i, 0, n) {
int su = 0;
rep(k, 0, n) su += A[i][k] & x[k];
(mul *= su) %= 4;
}
rep(i, 0, n) if(x[i]) mul *= -1;
(as += mul) %= 4;
return;
}
if(!bas[i][i]) rep(j, 0, 1) {
x[i] = j, dfs(i + 1);
rep(k, 0, n) if(bas[k][i]) x[k] ^= 1;
} else dfs(i + 1);
}
void solve() {
rep(i, 0, n) bas[i].reset();
rep(i, 0, n) {
bitset <302> nw = A[i];
rep(j, 0, n) if(nw[j]) {
if(bas[j][j]) nw ^= bas[j];
else { bas[j] = nw; break; }
}
if(nw[n + 1] && nw.count() == 1) return;
}
per(i, n, 0) if(bas[i][i]) rep(j, i + 1, n) if(bas[j][j] && bas[i][j]) bas[i] ^= bas[j];
rep(i, 0, n) x[i] = bas[i][n + 1];
dfs(0);
}
int main() {
srand(time(0));
for(cin >> T; T--;) {
scanf("%d", &n), as = 0;
rep(i, 0, n) A[i].reset();
For(i, 0, n) {
scanf("%s", s), A[i][n] = rand() & 1, A[i][n + 1] = 1;
For(j, 0, n) A[i][j] = s[j] - 48;
}
A[n][n] = A[n][n + 1] = 1;
solve();
rep(i, 0, n) A[i][n + 1] = 0, solve(), A[i][n + 1] = 1;
puts(as ? "NO" : "YES");
}
return 0;
}