网上大佬写的博客。。。我以为自己看懂了（假装看懂）。。。结果第二题就被卡住了。。。看不懂了。。
https://blog.sengxian.com/algorithms/linear-basis
https://www.cnblogs.com/vb4896/p/6149022.html
是我水平不够，看起来有点费劲(;´༎ຶД༎ຶ`)智商堪忧
还是视频看起来轻松很多：青涩的讲解，但是能听懂，给up主点赞！
目前的理解：线性基就是通过异或构建行阶梯矩阵，找到最大线性无关的向量组，去解决有关XOR的一些问题
数x对应的二进制为：
所谓线性基，就是线性代数里面的概念。一组线性无关的向量便可以作为一组基底，张起一个线性的向量空间，这个基地又称之为线性基。
第一个例子：
--->插入a[0]=7=0111:a[0]的
矩阵：
--->插入a[1]=2=0010：a[1]的
矩阵：
--->插入a[2]=3=0011，从高位向低位看起，因为
矩阵：
--->插入a[3]=4=0100，
至此，线性基对应的行阶梯矩阵已经构建完了，此外，通过构建过程可以知道最终的矩阵可以转化为如下内容：
p[2]、p[1]、p[0]都不为0，所以线性基的大小为num=3，a[4]中n=4，num<n
p[2]、p[1]、p[0]对应的向量是一个最大线性无关的向量组，因为num<n所以a[]中的数可以通过异或得到0，这点可以通过插入a[3]时出现0得到验证。当num=n时，这n个向量组成最大线性无关的向量组，根据线性无关的定义可以知道只有这些向量前面的系数都为0时才可以得到0。
注意：这里的p[2]、p[1]、p[0]进行异或相当于其对应的向量进行加法运算(二进制加法，没有进位)。
用新的数组L（或者一个vector<>）存不为0的p[i]，若求a[4]所能构成的异或的数中的第k小，k=
若求第k=1小，因为num!=n，所以可以异或出0，那么可异或出第1小的数就是0
若求第k=4小，因为num!=n，所以可以异或出0，所以k=k-1=3=0011，
第二个例子：
--->插入a[0]=9=1001，p[3]=a[3]
矩阵：
--->插入a[1]=11=1011，p[3]已经有数了，a[1]^=p[3]=0010，p[1]=a[1]，用下面的行消自己，用自己消下面的行(但都莫得消)
矩阵：
--->插入a[2]=5=0101，p[2]=a[2]，用下面的行消自己，用自己消下面的行(但都莫得消)
矩阵：
最终的矩阵相当于：其中线性基的大小num=3，n=3
用新的数组L存不为0的p[i],求a[3]能异或成的第k小，k=
因为线性基大小num=n,所以不能异或出0
若k=1=0001，
若k=5=1001，
综上所述：
终于写完原理了٩(˃̶͈̀௰˂̶͈́)و总算是懂了线性基了☆〜（ゝ。∂）
一般1≤a[i]≤1e18，最多60位，所以max_base设成60，p[max_base+3]，max_base别设置太大了，可能结果会错，我试过(´･Д･)」，就60吧！
模版：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
const int max_base=60;
ll t,n,q,x;
ll a[maxn],p[maxn+3];
vector<ll> v;
void solve()
{
v.clear();//清空啊啊啊！！！
memset(p,0,sizeof(p));//初始化啊啊啊！！！
for(int i=0;i<n;i++)
{
for(int j=max_base;j>=0;j--)//从高位向低位
{
if(a[i]>>j==0) continue;//该位上为0，对线性基这位没有有贡献
if(!p[j])//该行没数，直接填入
{
p[j]=a[i];
for(int k=j-1;k>=0;k--)
if(p[k] && p[j]>>k&1)
p[j]^=p[k];//下面的行消自己
for(int k=j+1;k<=max_base;k++)
if(p[k]>>j&1)
p[k]^=p[j];//自己消上面的行
break;//填入之后结束每一位上的遍历
}
else
a[i]^=p[j];//该行已经有数
}
}
for(int i=0;i<=max_base;i++)
if(p[i])
v.push_back(p[i]);
}
ll query(ll x)
{
if(v.size()!=n) x--;
if(x==0) return 0;//能得到0，第1小的数是0
if(x>=(1LL<<v.size())) return -1;//能得到0，x已经-1了，x最多达到2^v.size()-1;不能得到0，x最多就是v.size()-1
ll ans=0;
for(int i=0;i<=max_base;i++)
if(x>>i&1)
ans^=v[i];
return ans;
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt", "r", stdin);
scanf("%lld",&t);
for(int i=1;i<=t;i++)
{
printf("Case #%d:\n",i);
scanf("%lld",&n);
for(int j=0;j<n;j++)
scanf("%lld",&a[j]);
solve();
scanf("%lld",&q);
for(int j=0;j<q;j++)
{
scanf("%lld",&x);
printf("%lld\n",query(x));
}
}
return 0;
} SGU275:但是好像没法补题，求n个数异或得到的最大值,直接把非0的p[i]异或起来就完事了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
const int max_base=60;
ll n;
ll a[maxn],p[maxn+3];
void solve()
{
for(int i=0;i<n;i++)
{
for(int j=max_base;j>=0;j--)//从高位向低位
{
if(a[i]>>j==0) continue;//该位上为0，对线性基这位没有有贡献
if(!p[j])//该行没数，直接填入
{
p[j]=a[i];
for(int k=j-1;k>=0;k--)
if(p[k] && p[j]>>k&1)
p[j]^=p[k];//下面的行消自己
for(int k=j+1;k<=max_base;k++)
if(p[k]>>j&1)
p[k]^=p[j];//自己消上面的行
break;//填入之后结束每一位上的遍历
}
else
a[i]^=p[j];//该行已经有数
}
}
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt", "r", stdin);
ll ans=0;
scanf("%lld",&n);
for(int i=0;i<n;i++)
scanf("%lld",&a[i]);
solve();
for(int i=0;i<=max_base;i++)
if(p[i])
ans^=p[i];
printf("%lld\n",ans);
return 0;
}
京公网安备 11010502036488号