线性基

线性基

概述

通常可以解决有关异或的一些题目。

对于给定的数集 $A$,线性基是一个子集 $P\subset A$,其满足:

  • 原序列里面的任意一个数,都可以由线性基里面的若干个数按位异或得到;
  • 任意若干个数,异或和不为 $0$.
  • 是满足上述条件的最小子集。

能求出:给定集合的最大异或和。

构造

//插入一个long long范围内的整数
int p[65];
void insert(int x) {
    for(int i = 62; i >= 0; i--) {
        if(x & (1ll << i)) {
            if(!p[i]) { p[i] = x; break; }
            x ^= p[i];
        }
    }
}

在二进制下,$p[i]$ 代表线性基中,最高位是第 $i$ 位的元素。

显然每个数位最多需要一个元素,因为当 $p_i=2^i$ 时,所有数都能被线性基表出。

上面这段代码中,用 $x_i$ 表示 x 在运行过程中的取值,那么其含义为:要让 $x$ 能被线性基表出,则只需 $x_i$ 可以被线性基表出

循环第一次进行时,我们需要 $x$ 能被表出,用 $i$ 表示二进制下 $x$ 的最高位,则:

  • 若 $p_i$ 为空,$p_i\leftarrow x$,直接填入后跳出循环。
  • 若 $p_i$ 非空,由于 $p_i$ 已经可以被表出了,要想让 $x$ 能被表出,就只需要 $x\oplus p_i$ 可以被表出。所以让 $x\leftarrow x\oplus p_i$,注意到 $p_i\oplus x$ 的最高位会变小,会在后面的循环中被处理,这很合理。

若当循环结束时,$p_i\leftarrow x$ 还没有被执行过,说明 $x$ 在插入前就可以被线性基表出了。

查询异或最值

还没写完

前缀线性基

考虑线性基的插入过程,线性基上每一位的数,都是对应位上在原数列最左侧的数字。现在我们进行改变,使得线性基上每一位的数,都变成对应位上在原数列最右侧的数字。

代码实现:

struct Linear_Basis{
	int p[24], pos[24];
	void insert(int x, int id) {
		for(int i = 23; i >= 0; i--) {
			if(x & (1ll << i)) {
				if(!p[i]) { p[i] = x, pos[i] = id; break; }
				else if(id > pos[i]) { swap(pos[i], id), swap(x, p[i]); }
				x ^= p[i];
			}
		}
	}
	int qry_max(int l) {
		int ret = 0;
		for(int i = 23; i >= 0; i--)
			if(pos[i] >= l && (ret ^ p[i]) > ret) ret ^= p[i];
		return ret;
	}
} lb;

尽可能用右侧的数来作为基,所以要用 $x$ 替换掉 $p_i$ 的位置。

插入之后需要 $\mathrm{swap}(x, p_i)$,因为此时的线性基已经能表出 $x$ 了,但原先的 $p_i$ 不能被表示了。

直接取出所有 $pos_i\geq l$ 的 $p_i$,就是 $a_{[l,r]}$ 的线性基。

原因:还是要看上面插入函数流程的含义。若一个 $p_i$ 所对应的 $pos_i

 

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇