「みんなのプロコン 2019」E - Odd Subrectangles

この問題まではムーブが完璧だった。
E - Odd Subrectangles

問題

N行M列の、要素が0と1からなる行列Aが与えられる。行と列の部分集合(U, V)の組は2^{N+M}通りありえるが、その中で以下を満たすものを数え上げよ。

Aを(U, V)に制限したときにできる行列に含まれる1の個数は奇数である

解法

まず行の集合Uを固定しよう。このとき問題の条件をみたす列の集合Vは何通りあるだろうか? 簡単な考察で、以下の事実がわかる。

Uとの交差部分に含まれる1の個数が奇数であるような列全体の集合をKとする。(U, V)に制限した行列の中に1が奇数個あることと、|V \cap K|の大きさが奇数であることは同値である。そのようなVは、|K| = 0のとき0個、|K| > 0のときちょうど全組み合わせの半分(つまり2^{M-1}個)ある。

よって、|K| = 0となるようなUの個数を数え上げることができればよい。これは各行を行ベクトルと見做した時に、Uに含まれる列ベクトルの和が0であるようなUの個数と等しい。
各行について、それがUに含まれるかどうかを0/1の変数で表すことにすると、結局N次元の0/1ベクトルvであって、Z/2Z上で計算したときvA = 0となるものの個数を計算すれば良いことがわかる。Z/2Zは体であるため、普通の線形代数が適用できて、このようなvはker Aの住人、およびそれに限ることがわかる。|ker A| = 2^{dim (ker A)}であり、dim (ker A) = N - rank Aであるので、rank Aを計算すればよい。これはGauss-Jordanのアルゴリズムなどでできる。

登場する典型

Z/2Z上の線形代数
- rank, ker, ものの有り無しを0/1ベクトルと見做して線形代数に帰着させる

実装上の注意点

Gauss-Jordanは難しいので実装に気をつける

提出: Submission #4212889 - Yahoo Programming Contest 2019 (Rust)

// ModInt省略

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,
        a: [[i32; m]; n],
    }
    let mut a = a;
    let mut c = 0;
    for r in 0..m {
        if c >= n {
            break;
        }
        let mut c2 = None;
        for i in c..n {
            if a[i][r] == 1 {
                c2 = Some(i);
                break;
            }
        }
        if c2.is_none() {
            continue;
        }
        let c2 = c2.unwrap();
        a.swap(c, c2);
        for k in c + 1..n {
            if a[k][r] == 1 {
                for j in 0..m {
                    a[k][j] ^= a[c][j];
                }
            }
        }
        c += 1;
    }
    let two = ModInt::new(2);
    // eprintln!("n = {}, c = {}", n, c);
    let mut prod = two.pow(n as i64) - two.pow((n - c) as i64);
    prod *= two.pow(m as i64 - 1);
    puts!("{}\n", prod);
}

まとめ

ここまで完璧だっただけにFのミスが激痛ですね。