线性代数部分#

别问为什么不在数学部分

线性基#

其中 $cnt$ 表示基的大小

插入操作#

从高位到最低位贪心即可

1
bool insert(int x){
2
    for (int i=30;i>=0;i--){
3
        if (x>>i&1){
4
            if (!val[i]){
5
                val[i]=x;cnt++;
6
                return 1;
7
            }
8
            x^=val[i];
9
        }
10
    }
11
    return 0;
12
}

求第k小#

将 $k$ 二进制拆分，按位取就可以（ $0$ 的情况需要特判，这里只是计算目前基的第 $k$ 小）

1
int qry_kth(int k){
2
    int ans=0,ct=1<<cnt;
3
    for (int i=30;i>=0;i--){
4
        if (val[i]){
5
            if (k>(ct>>=1)){
6
                k-=ct;
7
                if (~ans>>i&1)ans^=val[i];
8
            }
9
            else if (ans>>i&1)ans^=val[i];
10
        }
11
    }
12
    return ans;
13
}

求x的排名#

这里我们计算小于等于 $x$ 的数的个数，首先需要记录一个异或和 $pre$ ，就是所选的 $val_{i}$ 的异或和。从大到小枚举每一位，我们知道， $val_{i}$ 有值的地方的 $1$ 一定能取到，我们可以维护 $pre$ 使得取到这些位置上的 $1$ ，对于 $val_{i}=0$ 的位置，如果 $x$ 与 $pre$ 不同时，说明我们知道所求位置了，判断一下是谁有 $1$ 就可以了。

1
int qry_rk(int x){
2
    int ans=0,ct=(1<<cnt),pre=0;x++;
3
    for (int i=30;i>=0;i--){
4
        if (val[i]){
5
            ans+=(x>>i&1)*(ct>>=1);
6
            if ((x^pre)>>i&1)pre^=val[i];
7
        }
8
        else if ((x^pre)>>i&1){
9
            if (x>>i&1)ans+=ct;
10
            break;
11
        }
12
    }
13
    return ans;
14
}

Linear_Algebra

https://fuwari.vercel.app/posts/linear_algebra/

Author

Ender子浪

Published at

2025-11-28

License