线性基基本操作于模板

谁借莪１个温暖的怀抱￠ 2023-10-09 12:54 51阅读 0赞

资料出处：[https://blog.csdn.net/a\_forever\_dream/article/details/83654397][https_blog.csdn.net_a_forever_dream_article_details_83654397]

[https://blog.csdn.net/qaq\_\_qaq/article/details/53812883][https_blog.csdn.net_qaq_qaq_article_details_53812883]

基础操作：

定义  
设数集T的值域范围为\[1,2n−1\]。  
T的线性基是T的一个子集A=\{a1,a2,a3,...,an\}。  
A中元素互相xor所形成的异或集合，等价于原数集T的元素互相xor形成的异或集合。  
可以理解为将原数集进行了压缩。

性质  
1.设线性基的异或集合中不存在0。  
2.线性基的异或集合中每个元素的异或方案唯一，其实这个跟性质1是等价的。  
3.线性基二进制最高位互不相同。  
4.如果线性基是满的，它的异或集合为\[1,2n−1\]。  
5.线性基中元素互相异或，异或集合不变。

维护  
插入  
如果向线性基中插入数x，从高位到低位扫描它为1的二进制位。  
扫描到第i时，如果ai不存在，就令ai=x，否则x=x⊗ai。  
x的结局是，要么被扔进线性基，要么经过一系列操作过后，变成了0。

bool insert(long long val)
    {
        for (int i=60;i>=0;i--)
            if (val&(1LL<<i))
            {
                if (!a[i])
                {
                    a[i]=val;
                    break;
                }
                val^=a[i];
            }
        return val>0;
    }

### 合并 ###

将一个线性基暴力插入另一个线性基即可。

L_B merge(const L_B &n1,const L_B &n2)
    {
        L_B ret=n1;
        for (int i=0;i<=60;i++)
            if (n2.d[i])
                ret.insert(n2.d[i]);
        return ret;
    }

查询  
存在性  
如果要查询x是否存于异或集合中。  
从高位到低位扫描x的为1的二进制位。  
扫描到第i位的时候x=x⊗ai   
如果中途x变为了0，那么表示x存于线性基的异或集合中。

最大值  
从高位到低位扫描线性基。  
如果异或后可以使得答案变大，就异或到答案中去。

long long query_max()
    {
        long long ret=0;
        for (int i=60;i>=0;i--)
            if ((ret^d[i])>ret)
                ret^=d[i];
        return ret;
    }

### 最小值 ###

最小值即为最低位上的线性基

long long query_min()
    {
        for (int i=0;i<=60;i++)
            if (d[i])
                return d[i];
        return 0;
    }

k小值  
根据性质3。  
我们要将线性基改造成每一位相互独立。  
具体操作就是如果i<j，aj的第i位是1，就将aj异或上ai。  
经过一系列操作之后，对于二进制的某一位i。只有ai的这一位是1，其他都是0。  
所以查询的时候将k二进制拆分，对于1的位，就异或上对应的线性基。  
最终得出的答案就是k小值。

void rebuild()
    {
        for (int i=60;i>=0;i--)
            for (int j=i-1;j>=0;j--)
                if (d[i]&(1LL<<j))
                    d[i]^=d[j];
        for (int i=0;i<=60;i++)
            if (d[i])
                p[cnt++]=d[i];
    }
    long long kthquery(long long k)
    {
        int ret=0;
        if (k>=(1LL<<cnt))
            return -1;
        for (int i=60;i>=0;i--)
            if (k&(1LL<<i))
                ret^=p[i];
        return ret;
    }

模板：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

struct L_B{
        long long d[61],p[61];
        int cnt;
        L_B()
        {
            memset(d,0,sizeof(d));
            memset(p,0,sizeof(p));
            cnt=0;
        }
        bool insert(long long val)
        {
            for (int i=60;i>=0;i--)
                if (val&(1LL<<i))
                {
                    if (!d[i])
                    {
                        d[i]=val;
                        break;
                    }
                    val^=d[i];
                }
            return val>0;
        }
        long long query_max()
        {
            long long ret=0;
            for (int i=60;i>=0;i--)
                if ((ret^d[i])>ret)
                    ret^=d[i];
            return ret;
        }
        long long query_min()
        {
            for (int i=0;i<=60;i++)
                if (d[i])
                    return d[i];
            return 0;
        }
        void rebuild()
        {
            for (int i=60;i>=0;i--)
                for (int j=i-1;j>=0;j--)
                    if (d[i]&(1LL<<j))
                        d[i]^=d[j];
            for (int i=0;i<=60;i++)
                if (d[i])
                    p[cnt++]=d[i];
        }
        long long kthquery(long long k)
        {
            int ret=0;
            if (k>=(1LL<<cnt))
                return -1;
            for (int i=60;i>=0;i--)
                if (k&(1LL<<i))
                    ret^=p[i];
            return ret;
        }
    }
    L_B merge(const L_B &n1,const L_B &n2)
    {
        L_B ret=n1;
        for (int i=60;i>=0;i--)
            if (n2.d[i])
                ret.insert(n1.d[i]);
        return ret;
    }

转载于:https://www.cnblogs.com/shuaihui520/p/11339072.html

[https_blog.csdn.net_a_forever_dream_article_details_83654397]: https://blog.csdn.net/a_forever_dream/article/details/83654397
[https_blog.csdn.net_qaq_qaq_article_details_53812883]: https://blog.csdn.net/qaq__qaq/article/details/53812883
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif