在算法竞赛中，有一种特殊的处理方式针对一组数的异或运算。在 $mod\ 2$ 域内，任意一个维度仅有零向量与单位向量，而异或正是一种非常便利的在 $mod\ 2$ 域内的”高斯消元“。
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
71
72
73
74
75
76
77
78
| struct LBase {
int dims = 0;
vector<ll> d;
bool zero = false;
LBase(int n = 62) : dims(n) {
d.resize(n);
}
bool insert(ll x) {
for (int i = dims - 1; i >= 0; i --) {
if (x & (1ll << i)) {
if(d[i]) {
x ^= d[i];
} else {
d[i] = x;
/* 下面的代码需要用到最小构造时加入
for(int j = i - 1; j >= 0; j --) {
if(d[j] && (d[i] >> j & 1) ) d[i] ^= d[j];
}
for(int j = dims - 1; j > i; j --) {
if(d[j] >> i & 1) d[j] ^= d[i];
}
------------------------------ */
break;
}
}
}
zero |= x == 0;
return x > 0;
}
ll get_max() {
ll x = 0;
for (int i = dims - 1; i >= 0; i --) if(d[i]) {
x = max(x, x ^ d[i]);
}
return x;
}
ll get_min() {
ll x = 0;
for(int i = 0; i < dims; i ++) if(d[i]) {
x = d[i];
break;
}
return x;
}
bool check_ex(ll x) {
for(int i = dims - 1; i >= 0; i --) {
if(x & (1 << i)) {
if(!d[i]) {
return false;
}
x ^= d[i];
}
}
return true;
}
void merge(const LBase &a) {
for (int i = a.dims - 1; i >= 0; i --) if(a.d[i]) {
insert(a.d[i]);
}
}
int get_ranks() {
int ranks = 0;
for(int i = 0; i < dims; i ++) {
ranks += (d[i] > 0);
}
return ranks;
}
// 求第 k 小， 需要用到最小构造
ll kth(ll k) {
ll res = 0, rks = get_ranks();
if(zero) k --;
if(k >= (1 << rks)) return -1;
for(int i = 0; i < dims; i ++) {
if(k & (1ll << i)) res ^= d[i];
}
return res;
}
};
|
2023 牛客多校 9 G#
Non-Puzzle: Game
题目大意
A,B 两人博弈，初始有 $n$ 个数，$a_1, a_2, …, a_n$，A 先手，每人可以任意选择两个数 $a_i,a_j$（$1\leq i,j\leq n$），并将 $a_i \bigoplus a_j$ 加入原数组中，先得到 $k$ 的人获胜。
题解
事实上，如果 A 第一回合无法获胜，那么就只有平局和 B 胜的情况。
那么 B 胜的情况事实上非常好考虑，即
$$
\forall i, j, t, a_i \bigoplus a_j \bigoplus a_t = k
$$
但是题目所给的 $n$ 非常大，显然上式不能用常规的方法证明，需要另寻他法。
通过对上式进行一些转化，可以写出：
$$
\forall i, j, t, (a_i \bigoplus k) \bigoplus (a_j \bigoplus k) = a_t\bigoplus k
$$
可以定义一种新的运算 $F$ 来定义上式，即：
$$
a_i F a_j = a_t
$$
原题就转化成了代数系统 $(a, F)$ 是闭包的。
最后根据异或线性基的性质，仅需证明由 $a_i \bigoplus k$ 构成的集合的秩的二次幂等于集合大小。
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
| struct LBase {
int dims = 0;
vector<ll> d;
LBase(int n = 62) : dims(n) {
d.resize(n);
}
bool insert(ll x) {
for (int i = dims - 1; i >= 0; i --)
if (x & ((ll)1 << i)) {
if(d[i]) {
x ^= d[i];
} else {
d[i] = x;
break;
}
}
return x > 0;
}
int get_ranks() {
int ranks = 0;
for(int i = 0; i < dims; i ++) {
ranks += (d[i] > 0);
}
return ranks;
}
};
void solve() {
int n, k;
cin >> n >> k;
set<int> s;
for(int i = 0; i < n; i ++) {
int x;
cin >> x;
s.insert(x);
}
for(int i : s) {
if(s.find(i ^ k) != s.end()) {
cout << "Alice\n";
return;
}
}
LBase lb;
int cnt = 0;
set<int> T;
for(int x : s) {
lb.insert(x ^ k);
T.insert(x ^ k);
}
int r = lb.get_ranks();
if(((1ll << r) == T.size())) {
cout << "Bob\n";
} else {
cout << "Draw\n";
}
}
|