Daniel_yuan's Blog

芙卡米天下第一可爱 n(*≧▽≦*)n

0%

线性基的瞎操作

1. 查找某个数 \(x\) 可以被给出基底 \(A\) 如何异或得到

把基底 \(A\) 做线性基,并且在线性基的同时维护线性基中每个元素是由基底中的哪些元素异或得到的,记作 \(S\),那么在查询的时候,把对应位置的 \(S\) 也一起异或,就可以得到最终所求。

2. 把基底 \(A\) 的一个数 \(A_i\) 与另一个数 \(x\) 交换,保证交换后基底 \(A'\) 仍然满足基底的性质

同上,在线性基的同时维护线性基中每个元素是由 \(A\) 中的哪些元素异或得到的,记作 \(S\)。先查询 \(x\) 怎么被 \(A\) 表示,因为 \(A'\) 依旧满足基底的性质,那么如果用 \(A\) 来表示 \(x\),那么 \(A_i\) 一定会被用到。所以 \(A_i\) 也可以用 \(A\) 中的数和 \(x\) 一起表示,那么就可以直接交换 \(x\)\(A_i\),然后去更新线性基中的每个位置的 \(S\) 即可。