牛客练习赛26 Xor序列(线性基)

题意

小a有n个数,他提出了一个很有意思的问题:他想知道对于任意的x, y,能否将x与这n个数中的任意多个数异或任意多次后变为y

链接:https://www.nowcoder.com/acm/contest/180/D
来源:牛客网

思路

首先异或任意多次其实就是异或一次,因为异或偶数次是没有意义的.其次假设任意多个数异或任意多次为W,根据题意$ x \oplus W = y$,也就是 $ x \oplus y = W$,那么我们的任务就是每次给出x,y判断集合中是否有一个子集异或值等于x^y.
这时候就是典型的线性基做法了

线性基介绍

线性基是某神牛牪犇发明的用来解决子集异或一类题目的算法。
先来介绍几个相关的概念:

向量空间

设V为n维向量的集合,如果集合V非空且集合V对于向量的加法及数乘两种运算封闭,那么就成V为向量空间。(也可以说是线性空间)

向量空间的基

设V是一个向量空间,如果r个向量$ \vec {a_1},\vec{a_2}…\vec{a_r}$ 且满足:
1.$\vec {a_1},\vec{a_2}…\vec{a_r}$ 线性无关
2.V 中任意一个向量都可由$\vec {a_1},\vec{a_2}…\vec{a_r}$ 线性表示
那么向量$\vec {a_1},\vec{a_2}…\vec{a_r}$ 就称为向量空间V的一个基,r称为向量空间V的维度,并称V为r维向量空间.

V的基就是向量组的最大无关组,r就是向量组的秩

线性无关

设有向量$\vec a_1,\vec a_2,…\vec a_n$,如果存在不全为0的$k_i$使得:
$ k_1 \vec a_1 + k_2 \vec a_2 + …k_n \vec a_n = 0$,那么就称他们线性相关,否则就是线性无关。

向量组线性无关的充要条件 R(A) = n,线性相关的充要条件R(A) < n,n为向量的个数

线性基

根据上面介绍的线性代数有最大线性无关组以及向量空间基的概念,线性基和它们类似.
异或可以看成是模2域下的加法运算,我们把每个数都转化成其对应的二进制,那么就可以看成是一个01构成的向量,所有这些向量就组成了一个线性空间。
上面说过向量空间的基,可以表示出向量空间的其他任何向量。所以对于这个问题我们就必须要找出空间的最大线性无关组,他们进行异或可以表示出该向量空间所有的数了.(这样得到的最大无关组就叫线性基)。
首先我们来证明一个性质:
取向量空间组中的两个向量a,b,将a,b中的某一个替换成$ a \oplus b$ 替换后向量组中的向量的线性组合得到的空间相同。也就是说,所能异或出的所有值和原来一样。
证明:
不妨把 b 变为c = a xor b. 对于一个值x如果原来她不需要b参与异或就能得到,那么值没变。
如果他需要b参加,那么b此时可以通过 c xor a 得到,因此替换后还是能得到x。综上,旧向量能得到的数我们新向量也能得到,因此替换前后能得到的向量空间是一样的,所以如果把向量组里的向量互相异或,最大线性无关向量组大小时不变的。因此可以用如下代码来求:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Guass()
{
for (int i=1;i<=sz;i++)
{
for (int j=62;j>=0;j--)//一般我们解决的问题都在longlong范围内,最多也就62位
{
if ((A[i]>>j)&1)
{
if (!P[j]) {P[j]=A[i]; break;}
else A[i]^=P[j];
}
}
}
for (int j=0;j<=62;j++) if (P[j]) r++;//r就是极大线性无关组的大小了
}

基本思想

从左往右扫描每个向量,对于第i个向量的第j位,如果前面已经有第j位为1的向量了,那么就把这个向量异或那个向量,一直找到最高位为1的未出现。最后得到的向量组,不考虑0向量,每个向量的最高位1的位置都是互不相同的,显然他们都是线性无关的。
这样我们就得到最大线性无关组,也就是线性基

性质

1.最高位1的位置互不相同。
2.任意一个可以用这些组合出的 $ \vec x$ ,组合方式唯一
假设x的组合方法不唯一, 也就是说 $x=a_1 xor a_2 ⋯ a_p = b_1 xor b_2 ⋯ b_qx=a_1 xor a_2 ⋯ a_p = b_1 xor b_2 ⋯ b_q$
那么 $x \oplus x = \vec a_1 xor \vec a_2 .. \vec a_p xor \vec b_1 …\vec b_p = 0$也就是说可以用这个最大无关组组合出$ \vec 0$这明显与定义相矛盾。

也就是说 可以用这个向量组里的向量组合出0向量, 与线性无关矛盾。 故组合方法唯一
3.线性基的任意一个子集异或和不为0.因为最高位1不一样,无论怎么取所有数中最大的最高位的1一定没办法处理。

关于本题

上面我们已经介绍了如何求线性基,那么现在我们只需要按照方法求出最大无关组。如何判断是否能凑乎来对应值呢?
我们对于给定的C,从高位开始如果第k位为1,那么$\vec a_k$是一定要用的,因为我们无关组的构造时 $\vec a_k$的最高位1一定在k,往后k位都不为1是没法构造的。(有人可能会问,那$ \vec a_k $前面的也可能第k位为1,但是我们不能用,因为C的最高位1为k,如果用前面的会在前面产生更高位
的1这是没法处理的).此时我们就让C xor $\vec a_k$ ,然后接着判断下面的最高位1,如果最后结果为0说明可以凑出来,否则凑不出来

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
#include<bits/stdc++.h>

using namespace std;
const int maxn = 32;
const int M = 31;
inline int read() {
char c = getchar();int x = 0,f = 1;
while(c < '0' || c > '9')
{ if (c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9')
x = x * 10 + c - '0',c = getchar();
return x * f;
}
int p[maxn];
void Insert(int x)
{
for(int i = M;i >= 0;--i)
{
if((x >> i ) & 1)
{
if(!p[i]) {p[i] = x;break;}
else x ^= p[i];
}
}
return ;
}
bool query(int x)
{
for(int i = M;i >= 0;--i)
{
if((x >> i) & 1)
{
if(!p[i]) return 0;
else x ^= p[i];
}
}
return x == 0;
}
int main()
{
int n,q;
while(cin >> n)
{
for(int i = 1;i <= n;++i)
{
int a = read();
Insert(a);
}
q = read();
while(q--)
{
int x,y;
x = read(),y = read();
if(query(x^y)) puts("YES");
else puts("NO");
}
}
return 0;
}


-------------本文结束感谢您的阅读-------------


本文标题:牛客练习赛26 Xor序列(线性基)

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2018年09月08日 - 13:09

最后更新:2018年12月20日 - 21:12

原始链接:https://statusrank.xyz/articles/1a4e1f2.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!

相关文章: