异或线性基
|
数学

356 字
|
7 分钟

仍待更新

1.资料来源

2.题目

  1. 洛谷-P3812
  2. HDU-3949

异或线性基

设数组$p$表示序列{$a_n$}的线性基，待插入数为$a$，下标从0开始。

将$a$转化为二进制，从高位开始，若当前位为1，并且线性基$p$的第$i$位上没有数，那就赋成当前值$x$。否则将$x$异或 $p_i$

插入操作(贪心做法)

void insert(int a)
{
    for(int i=M;i>=0;i--)
        if(a&(1LL<<i))
        {
            if(p[i]) a=a^p[i];
            else{p[i]=a; return ;}
        }
}

高斯消元法求线性基，可直接得到$p_i$的最小值，常用于下面求第$k$小异或值（用$zero$布尔值判断是否存在异或值为0的情况）

插入（高斯消元）

void gauss()
{
    int j=(1ll<<62),k=1,i;
    for(;j;j>>=1)
    {
        for(i=k;i<=n;i++)
        {
            if(a[i]&j) break;
        }
        if(i>n) continue;
        swap(a[i],a[k]);
        for(i=1;i<=n;i++)
        {
            if(i!=k && a[i]&j) a[i]^=a[k];
        }
        k++;
    }
    k--;
    if(k!=n) zero=true;
    else zero=false;
    n=k;
}

求异或最大值

纯贪心遍历线性基，逐个异或线性基{$p_i$}

int pmax()
{
    int ans=0;
    for(int i=M;i>=0;i--) ans=max(ans,ans^p[i]);
    return ans;
}

求k小值

利用上述 高斯消元插入法 得到的线性基。

将$k$先转成二进制，假如第$i$位为$1$，则$ans$异或线性基中第$i$个元素（注意不是直接异或 $p_{i-1}$）。

int getk_th()
{
	int ans=0;
	int k; cin>>k;
	if(zero) k--;
	if(!k) return 0;
	for(int i=n;i;i--)
	{
		if(k&1) ans^=a[i];
		k>>=1;
	}
	if(k) return -1;
	return ans;
}

下一篇