线性空间+线性基

· · 个人记录

向量：一行的矩阵或者一列的矩阵

线性空间：由一组向量通过线性组合能够表示的向量的集合

线性相关和线性无关：一组向量中，存在1个向量能够由其余向量线性组合得到，则称这组向量线性相关

线性空间的基底：一组线性无关的，数量最多的向量（极大线性无关的生成子集）

线性空间基底不是唯一的

线性空间的维度：一组基底的向量的个数

矩阵的秩：化成最简阶梯矩阵时，非零行向量或者非零列向量的个数

异或空间

由一组整数通过线性组合能够异或得到的整数集合

线性相关和线性无关：一组整数中，存在1个整数能够由其他整数异或得到，则称为线性相关

线性基：一组最大的线性无关的整数组合

一个异或空间的线性基的整数个数是相同的

线性基中的整数不可能异或得到0

线性基中的整数的最高位的位置互不相同

线性基的应用场景：

1.求一组整数异或得到的第k小数

2.求一个数是否能够被一组整数异或得到

普通方法:

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5005;
int a[MAXN];
int n,cnt,ans;
signed main()
{
    int ans=0;
    scanf("%lld",&n);
    cnt=n;
    for(register int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(register int i=1;i<=n;i++)
    {
        for(register int j=i+1;j<=n;j++)
            if(a[j]>a[i])swap(a[i],a[j]);
        if(!a[i])
        {
            cnt=i-1;
            break;
        }
        for(register int j=63;j>=0;j--)
            if(a[i]&((1ull)<<j))
            {
                for(register int k=1;k<=n;k++)
                    if(i!=k&&(a[k]&(1ull)<<j))
                        a[k]^=a[i];
                break;
            }
    }
    for(register int i=1;i<=cnt;i++)
        ans=max(ans,ans^a[i]);
    printf("%lld",ans);
    return 0;
}

构造方法求线性基：

1.从a[1]开始，尝试将每个元素插入线性基的集合

2.从最高位向最低位枚举，若第j位上还没有1，但在x在第j位有1，则将x插入集合p[j],否则x^=p[j]

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=65;
int p[MAXN]; //基底的集合 
int n,x,ans;
inline void check(int x) //将x尝试插入基底的集合 
{
    for(register int i=63;i>=0;i--)
    {
        if(x>>i) //提取x最高位1所在的位置 
        {
            if(p[i]==0) //如果第i位还没有任何一个向量有1 
            {
                p[i]=x;
                break;
            }
            else x=x^p[i];//如果第i位已经有1，则将x^p[i]得到新的x,再去继续找高位1 
        }
    }
    return;
}
signed main()
{
    scanf("%lld",&n);
    for(register int i=1;i<=n;i++)
    {
        scanf("%lld",&x);
        check(x);
    } 
    for(register int i=63;i>=0;i--)
        ans=max(ans,ans^p[i]);
    printf("%lld",ans);
    return 0;
}