跳转至

解决什么

约 1019 个字 185 行代码 预计阅读时间 6 分钟

  1. 第k大异或和
  2. 合法值是所有异或值的第几大
  3. 是否可以线性表出某个值
  4. 线性基合并
  5. x和线性基的异或最小值
  6. 1 到 n 的路径的最小异或和
  7. 所有异或值的和
  8. 带删线性基

前置知识

线性表出

一个向量如果可以被其他向量通过运算表示，那么称这个向量可以被线性表出。

例如2维平面上的任意向量，都可以被(0,1),(1,0)这组向量通过矢量合成与放缩表示

在XCPC中，通常是一个数可以被其他数通过异或表示

线性相关&线性无关

如果向量组中有一个向量可以被向量组其他向量线性表出，那么称这个向量组线性相关，否则线性无关

极大线性无关组

线性相关可以理解为有多余的向量，删完之后，就是极大线性无关组

线性基

向量组的极大线性无关组就是线性基，简称基

一个向量组可以对应多个基，因此需要构造出一种合法基

具体实现的选择

网络搜索得知有贪心构造，高斯消元构造。贪心构造里又分数组实现和vector实现。

这里只介绍vector实现

实现

构造基的过程是向已经得到的基，插入新元素，如果可以被基线性表出，则舍去，否则保留。空集的基是空集 

vector<ull> B;
void insert(ull x)
{
    for (ull &b : B)
        x = min(x, b ^ x);
    for (ull &b : B)
        b = min(b, b ^ x);
    if (x)
        B.push_back(x);
}
这种构造得到的基，有2个性质：

  1. 每个元素最高有效位各不相同

  2. 如果某一位是一个元素的最高有效位，则其他元素在这一位均为 0

性质证明

归纳证明：空集显然

插入新元素时，如果x变小，那么x在b的最高有效位是1，此时必须异或，否则之后没机会消掉x的这一位。

如果x在b的最高有效位是0，那么x要变大

一路操作下去，如果x是0，那么可以被线性表出，否则，新元素的最后结果的最高有效位一定和基中每个元素的最高有效位不同，即性质1。而且得到了x与集合内其他元素的组合异或最小值。

而第二个循环则是维护了性质2

K-th异或和

对基按照大小排序，即可根据k的二进制选择基求出第k小的异或和

不过还要考虑 0 的情况，如果构造的线性基比原集合小，说明原集合可以异或出 0 ，那么我们需要将 k 减去 1 。

如果要判断输入合法性，不同的异或和个数有 2^{cnt}-(!zero) 

void init2(int n)
{
    sort(B.begin(),B.end());
    if(B.size()<n)
        zero=1;
}
ull kthxorsum(ull k)
{
    k-=zero;
    ull ans=0;
    for(ull &b:B)
    {
        if(k&1)
            ans^=b;
        k>>=1;
    }
    return ans;
}

异或和rank

n个元素有 2^n 个子集，根据二进制反向处理

但是集合如果是线性相关的，就会有重复值，这里有个结论：

每个值都出现一样的次数，且这个次数 =2^{n-cnt} 

vector<int> rnk;
int msb(ull x)
{
    return 64 - __builtin_clzll(x);
}
void init2()
{
    for(ull &b:B)
        rnk.push_back(msb(b));
}
ull askrank(ull x)
{
    ull ans=0;
    for (int i = 0; i < cnt; ++i)
    {
        if (x >> rnk[i] & 1)
            ans +=1<<i;
    }
    return ans*fastpower(2,tot-cnt)+1;
}

查询线性表出

类似插入 

bool check(ull x)
{
    for (ull &b : B)
        x = min(x, b ^ x);
    return (!x);
}

线性基合并

把一个线性基插入另一个线性基即可 

void merge(linearBasis &o)
{
    for(ull &u:o)
        (*this).insert(u);
}

x和线性基的异或最小值

在性质证明里面介绍了 

ull minXorSumWithX(ull x)
{
    for (ull &b : B)
        x = min(x, b ^ x);
    return x;
}

小总结

到这里都是比较简单的内容，先做一个小板子 

typedef unsigned long long ull;
long long fast_power(long long base,long long exponent)
{
    long long result=1;
    for(;exponent>0;exponent>>=1)
    {
        if(exponent&1)
            result=result*base;
        base=base*base;
    }
    return result;
}
struct linearBasis
{
    vector<ull> B;
    int zero,cnt,tot;
    vector<int> rnk;
    void init()
    {
        B.clear();
        zero=tot=0;
    }
    void insert(ull x)
    {
        for (ull &b : B)
            x = min(x, b ^ x);
        for (ull &b : B)
            b = min(b, b ^ x);
        if (x)
            B.push_back(x);
        ++tot;
    }
    int msb(ull x)
    {
        return 63 - __builtin_clzll(x);
    }
    void init2()
    {
        sort(B.begin(),B.end());
        cnt=B.size();
        if(cnt<tot)
            zero=1;
        for(ull &b:B)
            rnk.push_back(msb(b));
    }
    ull kthxorsum(ull k)
    {
        k-=zero;
        ull ans=0;
        for(ull &b:B)
        {
            if(k&1)
                ans^=b;
            k>>=1;
        }
        return ans;
    }
    ull askrank(ull x)
    {
        ull ans=0;
        for (int i = 0; i < cnt; ++i)
        {
            if (x >> rnk[i] & 1)
                ans +=1<<i;
        }
        return ans*fast_power(2,tot-cnt)+1;
    }
    bool check(ull x)
    {
        for (ull &b : B)
            x = min(x, b ^ x);
        return (!x);
    }
    void merge(linearBasis &o)
    {
        for(ull &u:o.B)
            (*this).insert(u);
    }
    ull minXorSumWithX(ull x)
    {
        for (ull &b : B)
            x = min(x, b ^ x);
        return x;
    }
};

1 到 n 的路径的最小异或和

所有路径异或和，都可以由任意一条 1 到 n 路径的异或和与图中的一些环的异或和来组合得到。

从1先走到一个环，绕环一次，再原路返回，即可得到环的异或和，来路的异或和被抵消了。

A，B是两条1到n的路径，A，B组成环，如果A更优，走B前绕这个环一圈即可得到A的结果，所以是任意一条路径。

dfs搜出部分环，线性基自己可以解决环套环

最小异或和前面介绍过了 

typedef unsigned long long ull;
struct linearBasis
{
    vector<ull> B;
    void insert(ull x)
    {
        for (ull &b : B)
            x = min(x, b ^ x);
        for (ull &b : B)
            b = min(b, b ^ x);
        if (x)
            B.push_back(x);
    }
    ull minXorSumWithX(ull x)
    {
        for (ull &b : B)
            x = min(x, b ^ x);
        return x;
    }
}lb;
int vis[N],xorsum[N];
void dfs(int u,int sum)
{
    xorsum[u]=sum;
    vis[u]=1;
    for(auto &[v,w]:e[u])
    {
        if(vis[v])
            lb.insert(sum^w^xorsum[v]);
        else
            dfs(v,sum^w);
    }
}
dfs(1,0);
cout<<lb.minXorSumWithX(xorsum[n]);