线性基

作业部落链接：https://www.zybuluo.com/xzyxzy/note/1076707

前言

网上优秀博客：https://blog.sengxian.com/algorithms/linear-basis

一、理解

所谓基大概就是指
在一个集合内定义一种运算，用基的元素可以运算出所有用集合中的元素运算的结果
可以理解成基是一个集合的。。浓缩？

然后线性基呢就是这个运算是异或运算

二、性质

线性基中以每一位为最高位的1的数至多只有一个
所以把一个元素加入线性基中，那么

if(x&(<<j))
    {
        if(!p[j]){p[j]=x;break;}//一定要break！！
        else x^=p[j];
    }

三、题目

• [x] 【模板】线性基 https://www.luogu.org/problemnew/show/P3812
• [x] [BeiJing2011] 元素 http://www.lydsy.com/JudgeOnline/problem.php?id=2460
• [x] [WC2011] 最大XOR和路径 https://www.luogu.org/problemnew/show/P4151
• [ ] [SCOI2016] 幸运数字 https://www.luogu.org/problemnew/show/P3292
• [ ] [BZOJ3811] 玛里苟斯 http://www.lydsy.com/JudgeOnline/problem.php?id=3811
• [ ] [BZOJ2844] albus就是要第一个出场 http://www.lydsy.com/JudgeOnline/problem.php?id=2844
• [ ] [HDU2949] XOR https://vjudge.net/problem/HDU-3949
• [x] 2018.3.16考试题T1