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

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_e

前提知識

• mod2上でのガウスの消去法（掃き出し法）

解説

https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4221314

本当にちゃんと解きたい場合は線形代数をしっかり勉強しましょう。
自分はそこを疎かにしているので、インターネットの情報から典型っぽい部分を抽出して満足しました。
　
まず、この問題を行を2進数のビット列として見て、部分集合のxorが0にならない個数を計算する問題に帰着させよう。
これは、公式解説を見るしかない。
evimaさんも言っていたように「何個かのものからちょうど奇数個選ぶ方法が全体の半分」というのは覚えるべき典型っぽい。
（速攻で忘れそうだけど）
　
ここまで来ると、若干の典型適用ができる。
「xor 部分集合 数え上げ」みたいな感じでググってもいいが、ガウスの消去法を用いた方法がよく使われる。
他にも「行基本変形ができるところから見抜く」とか「O(N^3)からエスパー」とかを見かけた。
　
あとは、ガウスの消去法を作るなり、どっかから持ってくるなりして、ランクを求める。
すると、(2^N - 2^(N-R)) * 2^(M-1)が答え。
個人的に背景理論は全くわからないのだが、色々な引き出しができた気がする。
やっぱ、何事にも類題はあるものだなぁ。

int N, M;
int v[606];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;

    vector<vector<int>> v(N, vector<int>(M));

    rep(i, 0, N) rep(j, 0, M) {
        int a; cin >> a;
        v[i][j] = a;
    }

    int R = gaussianEliminationXOR(v);

    mint ans = ((mint(2) ^ N) - (mint(2) ^ (N-R))) * (mint(2) ^ (M - 1));
    cout << ans << endl;
}