tkdsheep-solution-0003

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
给出k个长度为n的二进制编码，再来很多次查询，每次查询都给出一个长度为n的编码，问能不能用这k个编码中的一部分来异或得到这个查询的编码

这个要用到线性空间以及基的概念，不懂的话可以去翻翻线性代数的书，简单的说就是先用高斯消元对k个编码进行变换，得到一组基，这个基只需要min(k,n)个编码即可
然后问题就变成给出的查询编码能不能用这组基来表示

什么是基？还是自己去看线性代数吧。。我在结尾给了维基百科的链接

我举个例子，以题目的sample为例

0011
1100
1010

这个k=3的那3个编码，高斯消元之后得到的结果是：（高斯消元怎么做，请参考wiki链接，这里的高斯消元只能自己写，没有模板）

1100
0110
0011

每个编码都有n=4位，可以看到，高斯消元后，如果查询的编码第一位是1，只有基里面的第一个元素1100能得到1
如果接下来查询的编码第二位也是1，那么就不能选基的第二个元素了，不然1100和0110异或会导致第二位变为0，不满组条件（因为基里面只有前两个元素是有可能第二位为1的）
这样依次O(n)扫下去，如果最后中间有不满足的情况，那么就说明无法用这组基来表示查询的编码

另外注意到n<=30，所以可以直接将编码转化成一个int值，然后直接位运算很方便


高斯消元
http://en.wikipedia.org/wiki/Gaussian_elimination
线性代数，基
http://en.wikipedia.org/wiki/Basis_%28linear_algebra%29


}}}

给出k个长度为n的二进制编码，再来很多次查询，每次查询都给出一个长度为n的编码，问能不能用这k个编码中的一部分来异或得到这个查询的编码
这个要用到线性空间以及基的概念，不懂的话可以去翻翻线性代数的书，简单的说就是先用高斯消元对k个编码进行变换，得到一组基，这个基只需要min(k,n)个编码即可
然后问题就变成给出的查询编码能不能用这组基来表示
什么是基？还是自己去看线性代数吧。。我在结尾给了维基百科的链接
我举个例子，以题目的sample为例
0011
1100
1010
这个k=3的那3个编码，高斯消元之后得到的结果是：（高斯消元怎么做，请参考wiki链接，这里的高斯消元只能自己写，没有模板）
1100
0110
0011
每个编码都有n=4位，可以看到，高斯消元后，如果查询的编码第一位是1，只有基里面的第一个元素1100能得到1
如果接下来查询的编码第二位也是1，那么就不能选基的第二个元素了，不然1100和0110异或会导致第二位变为0，不满组条件（因为基里面只有前两个元素是有可能第二位为1的）
这样依次O(n)扫下去，如果最后中间有不满足的情况，那么就说明无法用这组基来表示查询的编码
另外注意到n<=30，所以可以直接将编码转化成一个int值，然后直接位运算很方便
高斯消元
http://en.wikipedia.org/wiki/Gaussian_elimination
线性代数，基
http://en.wikipedia.org/wiki/Basis_%28linear_algebra%29