更好的阅读体验

还不会用 Markdown 的时候写的文章……重修&复习了一遍。主要修改的还是习题部分。

原来那篇低质量烂文已经删掉了awa 虽然这篇也没好到哪去

0 - 意义

线性基是向量空间的一组基，通常可以解决有关异或的一些题目。

简单讲就是由一个集合构造出来的另一个集合，这个集合大小最小且能异或出原来集合中的任何一个数，并且不能表示出除了原集合的其他数。

性质

1. 线性基能相互异或得到原集合的所有相互异或得到的值。

2. 线性基是满足性质1的最小的集合

3. 线性基没有异或和为 $0$ 的子集。

4. 假设线性基中有 $cnt$ 个数，线性基能异或出的数的集合大小为 $2^{cnt}-1$（去掉一个都不取），也就是说，线性基中不同的组合异或出的数都不一样。

1 - 构造

设当前插入的数是 $x$ ，线性基数组为 $a$ ，从高位向低位走，考虑所有为 $1$ 的当前位 $i$ ，

• 如果线性基的第 $i$ 位为 $0$ ，那么直接在这一位插入 $x$ ，退出；
• 否则，令 $x=x\oplus a[i]$
• 重复上述操作直到 $x=0$

如果退出循环的时候 $x=0$ ，那么说明原有的线性基已经可以表示 $x$ ，无需再插入；反之，则说明为了表示 $x$ 插入了一个新的元素。

void Insert( ll x )
{
    for ( int i=30; ~i; i-- )
        if ( x&(1ll<<i) )
            if ( !a[i] ) { a[i]=x; return; }
            else x^=a[i];
    flag=1;
}

检验存在

检查一个数是否能被某个线性基表示出来。

和插入类似，只要中途或者最后变成 $0$ 了，就说明能够表示。

bool check( ll x )
{
    for ( int i=30; ~i; i-- )
        if ( x&(1ll<<i) )
            if ( !a[i] ) return 0;
            else x^=a[i];
    return 1;
}

2 - 查询异或最值

最小值

查询最小值相对比较简单。

考虑在插入的过程中，每一次异或 $a[i]$ 的操作，$x$ 的二进制最高位都在降低，所以不可能插入两个二进制最高位相同的数。

此时线性基中的最小值异或上其他的数，必然会增大，所以直接输出线性基中的最小值即可。

注意要特判能否异或出 $0$ . 因为线性基有性质：没有异或和为 $0$ 的子集。特判也很简单，只要一个数在插入过程中没有被插入到某个 $a[i]$ ，那么就被异或成了 $0$ ，说明 $0$ 是可以取到的。

ll Query_min( ll res=0 )
{
    if ( fl ) return 0;    //flag 是 Insert 中传出来的变量，表示是否能表示 0 
    for ( int i=0; i<=30; i++ )
        if ( a[i] ) return a[i];
}

最大值

从高到低遍历线性基，设当前考虑到第 $i$ 位。如果当前答案 $res$ 的第 $i$ 位为 $0$ ，就将 $res=res\oplus a[i]$ ；否则不操作。或者说，更简便的写法是直接和异或后的值取 $\max$ （其实是一个道理，高位从 $0\to 1$ 一定是变大的嘛）

这是显然的，求最小值部分已经说过，线性基中数的最高位显然单调递减，那么每次这样的操作之后答案都不会变劣。

这是对序列中元素求相互异或的最大值。如果是另一个给定的数 $x$ ，那么用类似的方式可以解决，只需要把 $res$ 的初始值改变即可。

ll Query_max( ll res=0 )
{
    for ( int i=30; ~i; i-- )
        res=max( res,res^a[i] );
    return res;
}

模板

写到这里就可以写 模板题 了。代码：

//Author:RingweEH
const int N=55,MX=50;
int n;
ll a[N];

void Insert( ll x )
{
    for ( int i=MX; ~i; i-- )
        if ( x>>i&1 )
        {
            if ( !a[i] ) { a[i]=x; return; }
            x^=a[i];
        }
}

ll Query_mx( ll res=0 )
{
    for ( int i=MX; ~i; i-- )
        res=max( res,res^a[i] );
    return res;
}

int main()
{
    n=read();
    for ( int i=1; i<=n; i++ )
    {
        ll x=read(); Insert( x );
    }

    printf( "%lld\n",Query_mx() );

    return 0;
}

3 - 求第 k 小

首先，线性基的构造方式跟之前不太一样了，我们知道，线性基是以每个二进制为最高位存一个数的，容易想到把 k 二进制分解，这样的话，只需要改点限制：规定 $a[i]$ 的值最高位是第 $i$ 位，且在此基础上 $a[i]$ 最小。

考虑之前的 $a[i]$ ，它除了在第 $i$ 位有个 $1$ 外，在更低的位还有若干个 $1$ 。那是否可以用线性基中的某些数，尽量消去低位的那些 $1$ ？ 这个很好做，往线性基插入一个新数时，用这个 $a[i]$ 更新 $a$ 数组的其它所有值就行了。

详细做法：

• 对于低位

现在插入的一个数放到了 $a[i]$ ，它在一个更低的二进制位（设其为第 $j$ 位）上为 $1$ ，且 $a[j]$ 已被赋过值，那就把 $a[i]$ 更新为 $a[i]\oplus a[j]$ 。为了方便，从大到小枚举 $j$ 即可。

• 对于高位

只考虑低位显然不对，因为有可能 $a[i]$ 的第 $j$ 个二进制位为 $1$ ，而 $a[j]$ 此时可能没有值，但它以后被赋了值，这种情况下也应该用 $a[j]$ 更新 $a[i]$ 。我们只能用赋值晚的更新赋值早的，所以对于插入的一个数 $a[i]$ ，不仅要用更低位的 $a[j]$ 更新它，还要用它更新更高位的 $a[j]$ 。依然从大到小枚举 $j$ 。

代码：

for ( int i=N; ~i; i-- )
    if ( x>>i&1 )
    {
        if ( a[i] ) x^=a[i];
        else
        {
            a[i]=x;
            for ( int j=i-1; ~j; j-- )
                if ( a[j] && (a[i]>>j&1) ) a[i]^=a[j];
            for ( int j=N; j>i; j-- )
                if ( a[j]>>i&1 ) a[j]^=a[i];
            return;
        }
    }

其实这才是线性基的通用构造方式（比如对于模板题，多出来的要求对答案没有影响，因此该构造方案可以兼容使用）。

换个角度看这个构造方式，其实就是标准的高斯消元，所谓的把不在对角线上的 $1$ 能消掉就消掉，其实也就是让每行的数最小。

如上改变线性基的构造方式后，把 $k$ 二进制分解，若第 $i$ 位为 $1$ 就把 $ans$ 异或上 $p_i$ 即可。

注意也要特判能否异或出 $0$ ，并且在插入完之后要压缩线性基数组，只留下 $a[i]\neq 0$ 的部分。（这个显然，为 $0$ 相当于是无效位，对 $k$ 没有任何贡献，当然也不能算进位数里面）

模板题

//Author:RingweEH
const int N=63,M=65;
int n,cnt;
ll a[M],b[M];
bool fl=0;

void Insert( ll x )
{
    for ( int i=N; ~i; i-- )
        if ( x>>i&1 )
        {
            if ( a[i] ) x^=a[i];
            else
            {
                a[i]=x;
                for ( int j=i-1; ~j; j-- )
                    if ( a[j] && (a[i]>>j&1) ) a[i]^=a[j];
                for ( int j=N; j>i; j-- )
                    if ( a[j]>>i&1 ) a[j]^=a[i];
                return;
            }
        }
    if ( x==0 ) fl=1;
}

int main()
{
    int T=read();
    for ( int cas=1; cas<=T; cas++ )
    {
        memset( a,0,sizeof(a) ); fl=0; cnt=0;

        n=read();
        for ( int i=1; i<=n; i++ )
        {
            ll x=read(); Insert( x );
        }

        for ( int i=0; i<=N; i++ )
            if ( a[i] ) b[cnt++]=a[i];
        int q=read(); printf( "Case #%d:\n",cas );
        while ( q-- )
        {
            ll k=read(),ans=0; k-=fl;
            if ( k>=(1ll<<cnt) ) { printf( "-1\n" ); continue; }
            for ( int i=0; i<cnt; i++ )
                if ( k>>i&1 ) ans^=b[i];
            printf( "%lld\n",ans );
        }
    }

    return 0;
}

4 - 习题

也许大概或许可能是按难度排序的吧（

彩灯

有一个长度为 $N$ 的01串，初始全 $0$ 。给出 $M$ 个操作，每个操作能使特定的几位取反，问能产生几种不同的 $01$ 串。

Solution

显然是裸题。将每个操作看成一个数，构造线性基，题目也就是问能表示出多少个数。

注意到有性质：

假设线性基中有 $cnt$ 个数，线性基能异或出的数的集合大小为 $2^{cnt}-1$（去掉一个都不取）

那就做完了。不过这题全 $0$ 也算一种方案，不需要 $-1$ .

我怎么又没看见取模（悲）

//Author:RingweEH
const int N=55,MX=50;
const ll Mod=2008;
int n,m;
ll a[N],cnt=0;
char s[N];

void Insert( ll x )
{
    for ( int i=MX; ~i; i-- )
        if ( x>>i&1 )
        {
            if ( !a[i] ) { a[i]=x; cnt++; return; }
            x^=a[i];
        }
}

int main()
{
    n=read(); m=read();
    for ( int i=1; i<=m; i++ )
    {
        scanf( "%s",s ); ll x=0;
        for ( int j=0; j<n; j++ )
        {
            x<<=1;
            if ( s[j]=='O' ) x|=1;
        }
        Insert( x );
    }

    printf( "%lld\n",(1ll<<cnt)%Mod );

    return 0;
}

最大XOR和路径

给定一个边权为非负整数的无向连通图，求 $1$ 到 $N$ 的路径，使得边权异或和最大。点边可以重复经过。

$N\leq 5e4,M\leq 1e5,D_i\leq 1e18$ .

Solution

做法很简单：找出所有环，扔到线性基里，然后随便找一条路径作为初始值，求异或最大值即可。

考虑为什么是对的。

首先找环肯定是没有疑问的，因为重复走两遍相当于没有走，唯一能产生变数的就是环了。

然后考虑为什么随便一条路径就行。假设存在至少两条，设为 $path_1,path_2$ ，那么它们本身就构成了一个大环，异或一下就能得到对方。因此只要任意一条路径+所有环就好了。

//Author:RingweEH
const int N=5e4+10;
struct Edge
{
    int to,nxt; ll val;
}e[N<<2];
int head[N],tot=0,n,m;
ll path[N],a[64];
bool vis[N];

void Add( int u,int v,ll w )
{
    e[++tot].to=v; e[tot].nxt=head[u]; head[u]=tot; e[tot].val=w;
}

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

void Dfs( int u,int fa,ll now )
{
    vis[u]=1; path[u]=now;
    for ( int i=head[u]; i; i=e[i].nxt )
    {
        int v=e[i].to;
        if ( v==fa ) continue;
        if ( !vis[v] ) Dfs( v,u,now^e[i].val );
        else Insert( path[v]^now^e[i].val );
    }
}

int main()
{
    n=read(); m=read();
    for ( int i=1; i<=m; i++ )
    {
        int u=read(),v=read(); ll w=read();
        Add( u,v,w ); Add( v,u,w );
    }

    Dfs( 1,0,0 ); ll ans=path[n];
    for ( int i=62; ~i; i-- )
        ans=max( ans,ans^a[i] );

    printf( "%lld\n",ans );

    return 0;
}

albus就是要第一个出场

给定一个长度为 $n$ 的序列 $A$ ，将所有 $A$ 的子集的异或和从小到大排成序列 $B$ ，求一个数在 $B$ 中第一次出现的下标。

Solution

还是用这个性质：

假设线性基中有 $cnt$ 个数，线性基能异或出的数的集合大小为 $2^{cnt}-1$（去掉一个都不取）

然后注意到除了这 $cnt$ 个数，还有 $n-cnt$ 个，而它们所能组成的异或和一定能被线性基中的数表示出来，也就相当于我们有 $2^{n-cnt}$ 个异或和为 $0$ 的子集。那么就是，所有能异或出的数的集合中，每个数在 $B$ 序列里都出现了 $2^{n-cnt}$ 次。我们只需要查询数 $x$ 在不重复的序列中的排名 $rk$ ，然后 $ans=rk\times2^{n-cnt}+1$ 即可。

现在考虑如何求排名。从高到低枚举每一位 $a[i]\neq 0$ 的位置，如果 $x$ 的当前位为 $1$ ，那么就是比 “当前位为 $0$ 的 $2^{n-cnt}$ 个异或和”都要大，就加上这一部分的贡献；否则不加。（注：这里的 $cnt$ 指的是到当前位位置，$a[i]\neq 0$ 的个数。这应该很好理解，因为如果当前这个高位为 $1$ ，那么无论后面怎么取，都比高位为 $0$ 的要大）

被位运算优先级坑了一发 /kk

//Author:RingweEH
const int N=1e5+10,M=30,Mod=10086;
int n,a[M+5];

ll power( ll a,ll b )
{
    ll res=1;
    for ( ; b; b>>=1,a=a*a%Mod )
        if ( b&1 ) res=res*a%Mod;
    return res;
}

void Insert( int x )
{
    for ( int i=M; ~i; i-- )
        if ( x>>i&1 )
        {
            if ( !a[i] ) { a[i]=x; return; }
            x^=a[i];
        }
}

ll Query_rk( int x )
{
    int cnt=0; ll ans=0;
    for ( int i=M; ~i; i-- )
        if ( a[i] )
        {
            cnt++;
            if ( x>>i&1 ) ans=(ans+power(2ll,n-cnt))%Mod;
        }
    return ans;
}

int main()
{
    n=read();
    for ( int i=1; i<=n; i++ )
        Insert( read() );

    ll Q=read(); ll ans=Query_rk(Q);

    printf( "%lld\n",(ans+1)%Mod );

    return 0;
}

新Nim游戏

在 Nim 游戏的第一轮，允许两个玩家特殊操作：可以拿走若干个整堆，可以一堆都不拿，但是不能全部拿走。其余同 Nim。

问先手是否必胜，如果是那么给出第一轮拿的最小数量。

Solution

其实先手肯定必胜，第一次拿的时候只剩下一堆就好了。

那么问题在于如何让第一轮拿走的数量最小。

显然可以发现，先手第一轮拿完之后不能剩下异或为 $0$ 的子集。而这显然是个线性基（性质 $3$ ），也就是要构造和最大的一组线性基。

那么将每一堆排序，然后依次尝试加入线性基，并求出所有成功加入的数之和即可。

//Author:RingweEH
const int N=110,M=30;
int n,a[35],b[N];

bool Insert( int x )
{
    for ( int i=M; ~i; i-- )
        if ( x>>i&1 )
        {
            if ( !a[i] ) { a[i]=x; return 1; }
            x^=a[i];
        }
    return 0;
}

int main()
{
    n=read(); ll sum=0;
    for ( int i=1; i<=n; i++ )
        b[i]=read(),sum+=b[i];

    sort( b+1,b+1+n ); ll ans=0;
    for ( int i=n; i>=1; i-- )
        if ( Insert(b[i]) ) ans+=b[i];

    printf( "%lld\n",sum-ans );

    return 0;
}

元素

给定一个长度为 $n$ 的序列 $A[i][0/1]$ ，求一个子集，满足 $A[i][0]$ 的异或和不为 $0$ 的情况下，$A[i][1]$ 和最大。

Solution

神笔题，直接按照 $A[i][1]$ 排序，然后依次尝试插入即可。和上题差不多。

//Author:RingweEH
const int N=1010,M=60;
struct Node
{
    ll num; ll val;
    bool operator < ( const Node &tmp ) const { return val<tmp.val; }
}b[N];
int n;
ll a[M];

bool Insert( ll x )
{
    for ( int i=M; ~i; i-- )
        if ( x>>i&1 )
        {
            if ( !a[i] ) { a[i]=x; return 1; }
            x^=a[i];
        }
    return 0;
}

int main()
{
    n=read();
    for ( int i=1; i<=n; i++ )
        b[i].num=read(),b[i].val=read();

    sort( b+1,b+1+n ); ll ans=0;
    for ( int i=n; i>=1; i-- )
        if ( Insert(b[i].num) ) ans+=b[i].val;

    printf( "%lld\n",ans );

    return 0;
}

装备购买

$n$ 个装备，每个装备 $m$ 个属性，每个装备还有个价格。如果手里有的装备的每一项属性为它们分配系数（实数）后可以相加得到某件装备，则不必要买这件装备。求最多装备下的最小花费。

Solution

“能被已有的装备组合出来”这一点很像线性基，但这里不再是异或线性基了，而是实数。

回归本真的线性基，可喜可贺

其实方式和异或线性基差不多，不过是把原来的 $x=x\oplus a[i]$ 换成了消元（具体参考高斯消元的方式），之前 $a[i]$ 记录的是每一位上留下的那个数，现在就记录一个位置，使得矩阵中第 $i$ 列（也就是第 $i$ 个变量）只有 $a[i]$ 这一行不为 $0$ （对应高斯消元中把每一行的方程消成只剩下一个变量， $a[i]$ 记录的是第 $i$ 个变量所在的方程）。每次找当前行不为 $0$ 的列 $j$ ，如果 $a[j]$ 还没有值就赋值并退出，否则就用 $c[i][j]/c[a[j]][j]$ 乘上 $c[a[j]][k]$ 去减 $a[i][k]$ 。不会高斯消元的你试试看怎么消元解多元方程就好了吧

然后要求最小花费，那就排个序即可。

精度yyds！ 要开 long double 或者把 $eps$ 调成 $1e-5$ .

//Author:RingweEH
const int N=510;
const db eps=1e-5;
struct Vector
{
    db a[N]; int val;
    db &operator [] ( const int &x ) { return a[x]; }
    bool operator < ( const Vector&tmp ) const { return val<tmp.val; }
}c[N];
int n,m,a[N];


int main()
{
    n=read(); m=read();
    for ( int i=1; i<=n; i++ )
        for ( int j=1; j<=m; j++ )
            scanf( "%lf\n",&c[i][j] );
    for ( int i=1; i<=n; i++ )
        c[i].val=read();

    sort( c+1,c+1+n ); int cnt=0; ll ans=0;
    for ( int i=1; i<=n; i++ )
        for ( int j=1; j<=m; j++ )
        {
            if ( fabs(c[i][j])<eps ) continue;
            if ( !a[j] ) { a[j]=i; cnt++; ans+=c[i].val; break; }
            db tmp=1.0*c[i][j]/c[a[j]][j];
            for ( int k=j; k<=m; k++ )
                c[i][k]-=tmp*c[a[j]][k];
        }

    printf( "%d %lld\n",cnt,ans );

    return 0;
}