yukicoder No.803 Very Limited Xor Subset

この手の問題は最近割と見る印象がある。
No.803 Very Limited Xor Subset - yukicoder

問題

長さNの整数列Aがある。以下の条件を満たす部分列Sの個数をmod 10^9 + 7で求めよ:

  • Sのxor和はX
  • Sは以下のM個の条件(i = 1, ..., M)を満たす
    • L[i]番目からR[i]番目の要素の中でSに含まれるものの個数を2で割った余りはtype[i]である

制約

  • 1 <= N <= 300
  • 0 <= M <= min(300, N(N - 1) / 2)
  • 0 <= X, A[i] <= 10^9
  • 1 <= L[i] <= R[i] <= N
  • 入力は全て整数

解法

A[i]やXを長さ30の0/1ベクトルとみなす。選ぶ個数についての制約は次のようにエンコードできる:

  • j個目の制約用に、A[i]やXに列を追加する(30+j列目になる)。A[i]については、iがL[j]からR[j]に含まれていたらその列は1にする。Xについては、type[j]にする。

こうした場合、元の問題で全ての制約を満たすことと、この問題でAの部分列Sの要素ごとのxorがXになっていることは同値。そのようなSの個数を数え上げればよい。

線形代数を使うと、求めるSの個数はA[i]たちで生成できる空間にXが要素として含まれていたら|ker A| = 2^{dim (ker A)}、含まれていなければ0であることがわかる。この手の計算はGauss-Jordanの消去法ででき、計算量はO(N * M * min(N, M))である。

登場する典型

  • 使用するかしないかをGF(2)の要素と思って線形代数をする
    • Gauss-Jordanの消去法
  • rank A + dim (ker A) = dim cod A
    • 特定の0/1ベクトルをxor和として実現する方法を数えたい場合にかなりよく見るテク
  • 制約をエンコードするために列を追加

実装上の注意点

  • Gauss-Jordanの消去法はそこそこ間違えやすいので気をつける
  • 数え上げだが実質的にはdim kerを求める問題なので、サンプルがあっているからといって過信しない

提出: #325170 (Rust)

// ModInt省略

// returns (rank(a), dim ker(a))
fn gauss_elim_gf2(a: &mut [Vec<i32>], b: &mut [i32]) -> Option<(usize, usize)> {
    let n = a.len();
    let m = b.len();
    let mut row = 0;
    for col in 0..m {
        if row >= n { break; }
        let mut row2 = None;
        for i in row..n {
            if a[i][col] == 1 {
                row2 = Some(i);
                break;
            }
        }
        if row2.is_none() { continue; }
        let row2 = row2.unwrap();
        a.swap(row, row2);
        for k in row + 1..n {
            if a[k][col] == 1 {
                for j in 0..m {
                    a[k][j] ^= a[row][j];
                }
            }
        }
        if b[col] == 1 {
            for j in 0..m {
                b[j] ^= a[row][j];
            }
        }
        row += 1;
    }
    for i in 0..m {
        if b[i] != 0 { return None; }
    }
    Some((row, n - row))
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize,
        m: usize,
        x: i64,
        a: [i64; n],
        tlr: [(i32, usize1, usize); m],
    }
    let mut mat = vec![vec![0; 30 + m]; n];
    for i in 0..n {
        for j in 0..30 {
            mat[i][j] = if (a[i] & 1 << j) != 0 { 1 } else { 0 };
        }
    }
    let mut b = vec![0; 30 + m];
    for i in 0..30 {
        b[i] = if (x & 1 << i) != 0 { 1 } else { 0 };
    }
    for i in 0..m {
        let (t, l, r) = tlr[i];
        for j in l..r {
            mat[j][30 + i] = 1;
        }
        b[30 + i] = t;
    }
    match gauss_elim_gf2(&mut mat, &mut b) {
        Some((_, ker)) => {
            puts!("{}\n", ModInt::new(2).pow(ker as i64));
        },
        None => {
            puts!("0\n");
        },
    }
}

まとめ

この手の線形代数をやる問題は結構すき (解けるので)