首页 > 技术文章 > 关于带删除线性基

lnzwz 2021-02-24 20:48 原文

线性基,是可以删除的。
维护哪些数在线性基中,以及维护的每个线性基如何用它们表示,还有不在线性基中的数如何表示。
删除一个数\(x\)时,分类讨论。
若这个数不在线性基中,直接删除即可。
否则,就要消除它的影响。
找到一个不在线性基中,且需要\(x\)来表示的数\(y\)
如果找到了,那么把\(y\)加入线性基中,\(x\)可以用\(y\)和其它的基表示。
把它代入到其他的数的表示内,就可以消去这个\(x\)
其中,按照最高位维护的线性基无需改变,但它们的表示方法需要改变。
如果找不到,那么说明基的大小应当减一。
找到维护的线性基内,最小的需要用\(x\)表示的数\(z\)
然后,把维护的其他的需要用\(x\)表示的线性基都异或上\(z\)。这样就消除了\(x\)的影响。
\(z\)这个基就没有了,同时因为它是最小的,所以其他维护的基的最高位都不会改变。

void insert(int i,bitset<1000> &bi,int s)
{
    ij[i]=false;bs[i]=0;
    for(int j=s-1;j>=0;j--)
    {
        if(bi[j])
        {
            if(ji[j]==0)
            {
                ji[j]=bi;r+=1;ij[i]=true;
                bj[j]=bs[i];bj[j][i]=true;
                break;
            }
            else
            {
                bi^=ji[j];
                bs[i]^=bj[j];
            }
        }
    }
}
void del(int i,int n,int m)
{
    if(!ij[i])return;
    int z=-1;
    for(int x=0;x<n;x++)
    {
        if(!ij[x]&&bs[x][i])
        {
            z=x;
            break;
        }
    }
    if(z!=-1)
    {
        ij[z]=true;
        bitset<1000> t=bs[z];
        t[z]=true;
        for(int x=0;x<n;x++)
        {
            if(bs[x][i])
                bs[x]^=t;
        }
        for(int x=0;x<m;x++)
        {
            if(ji[x]!=0&&bj[x][i])
                bj[x]^=t;
        }
        return;
    }
    else
    {
        for(int x=0;x<m;x++)
        {
            if(ji[x]!=0&&bj[x][i])
            {
                z=x;
                break;
            }
        }
        bitset<1000> t=bj[z],o=ji[z];
        ji[z]=0;r-=1;
        for(int x=0;x<m;x++)
        {
            if(ji[x]!=0&&bj[x][i])
            {
                ji[x]^=o;
                bj[x]^=t;
            }
        }
    }
}

推荐阅读