线性基学习笔记

AC_Lover · 2025-02-17 08:02:38 · 算法·理论

（异或） 线性基性质：

①线性基对应的序列中任意一个数都可以由线性基中的一些数异或得到

②线性基中任意一些数异或都不得0

③线性基的在满足性质的条件下大小是最小的

插入(构造)：

void Insert(ll x)
{
    for (int i=62;i>=0;i--)
    {
        if ((x>>i)&1)
        {
            if (!p[i]) 
            {
                p[i]=x;
                return;
            }
            else x^=p[i];
        }
    }
}

查询异或起来可以得到的最大值：

ll get_max()
{
    ll res=0;
    for (int i=62;i>=0;i--) res=max(res,res^p[i]);
    return res;
}

查询是否可以异或得到一个数：

bool check(ll x)
{
    for (int i=62;i>=0;i--)
    {
        if ((x>>i)&1)
        {
            if (!p[i]) return false;
            else x^=p[i];   
        }   
    }   
    return true;
} 

查询异或起来可以得到的最小值：

ll get_min()
{
    for (int i=0;i<=62;i++)
    {
        if (p[i])
        {
            return p[i];
        }
    }
}