AGC045 A - Xor Battle

atcoder.jp

「ある正の整数の集合 A から好きなものを選んで XOR をとり、Kを作ることができるか？」という問題を解く。この問題は集合から作りうる数を全て列挙するのではなく、集合の基底をとり、そこから K が作れるかを考えれば良い。

基底は以下のようにして作れる。

let mut base = vec![];
for i in (0..n) {
    let mut a = a[i];
    for &b in base.iter() {
        if a ^ b < a {
            a ^= b;
        }
    }
    if a != 0 {
        base.push(a);
    }
}

sugoi