[ABC348] F - Oddly Similar

[Q] F - Oddly Similar

考察
O(2000^3)をどうbitsetにしようか、という思考を最初から最後まで考えていた。どうまとめればいいかわからなかった。
解説ACを具体的に処理する。

1. まずj列を固定して考える
2. i(0 <= i < N) 行を探索する。
用意するbitsetは2つで、
tmp: maxA * maxN の二次元配列データ。j列目だけを見た時に、どの行とどの行が似ているかを、Aごとに管理。
is_odd: maxN * maxM の二次元配列データ。0~j列目まで見た時点で、i行目がどの行と似ているかを管理。

3. まずtmpを入れる。
tmp[A[i][j]] = 似ている行id
を管理する。
tmp[3] = 00011 …A=3の行は0,1行目。

4. 次に、i行目はどの行と似ているかというbitsetデータis_oddを管理する。
is_odd^tmpをすれば更新可能。
is_odd[0] = 01001 .. 0行目は0,3行目と似ている。

5. すべての列を見終わった。何が答えになる？
is_odd[0~M]の.count()の総和を考える。
a. もしMが奇数なら、自分自身を加算してしまっているので-Nする。
b. (0, 1)が似ているデータと(1, 0)が似ているデータの2つを加算しているので/2すればいい。

実装

constexpr ll maxA = 1000;
constexpr ll maxN = 2000;
constexpr ll maxM = 2000;
int main()
{
  cincout();

  ll N, M;
  cin >> N >> M;
  vector A(N, vector<ll>(M));
  rep(i, N) rep(j, M)
  {
    cin >> A[i][j];
  }
  vector<bitset<maxM>> is_odd(N);
  vector<bitset<maxN>> tmp(maxA);
  /*
  3 3
  1 2 3
  1 3 4
  2 3 4
  */
  rep(j, M)
  { // 列を固定
    rep(i, N)
    { // 行探索
      tmp[A[i][j]].set(i); // 1 1 2
      /*
        tmp[1]: 00001
        tmp[1]: 00011 j列目を見た時点で、1がかぶってるのはi:0,1
        tmp[2]: 00100
      */
    }
    rep(i, N)
    {
      is_odd[i] ^= tmp[A[i][j]];
      /*
        is_odd[0]: 00011 今時点で0は0,1が似ている
        is_odd[1]: 00011 今時点で1は0,1が似ている
        is_odd[2]: 00100 今時点で2は2が似ている
      */
    }
    // 復元
    rep(i, N)
    {
      tmp[A[i][j]].reset(i);
    }
  }
  ll ans = 0;
  rep(i, N)
  {
    ans += is_odd[i].count();
    /*
      is_odd[0]: 00011 0は0,1が似ている
      is_odd[1]: 00011 1は0,1が似ている
      is_odd[2]: 00100 2は2が似ている
    */
  }
  if (M % 2 == 1)
  { // 自分を足しているので引く
    ans -= N;
  }
  cout << ans / 2 << endl;
}

https://atcoder.jp/contests/abc348/submissions/52136667