2018 codeFlyer 本選 D - 数列 XOR (600 点)

本番、最後には綺麗な解法になったけど、何度も WA を出して大変だったん。

問題へのリンク

問題概要

要素の数列 が与えられる。この数列に以下の操作を好きな回数だけ繰り返して数列 にできるかどうかを判定せよ。

【操作】
を xor に置き換えるか、 を xor に置き換えるかのいずれかを行う。

制約

• 
• 

考えたこと

XOR 操作に関する問題。まずはサンプル確認しつつ様相を掴む。

• xor だけでなく = xor もできそう (他に影響残さずに)
• もっとすごく頑張れば xor もできそうだし、一般に xor (他に影響残さずに)

という感じのことをひたすら考えていた。それより先に「隣り合う二項の swap」ができることを発見すると感銘である。 と とが隣り合っているとき、

と
↓
xor と
↓
xor と 　(左から右へ)
↓
と 　(右から左へ)

こうして、隣り合う と とが swap できることがわかった。隣り合う 2 数が swap できるということは、任意の 2 つが swap できるし、任意の並び替えができる。

というわけで、上で予想した通りの xor もできる。一旦 と とを入れ替えておいて、 を xor して、もう一度元に戻せば良い。

さて、以上の操作というのは実は「行列の掃き出し法」のような感じになっている。各 を二進法で表してそれを 0-1 ベクトル (横ベクトル) だと思うと、数列 は、 × 60 の行列 ( とする) になる。この視点で、上の結果を整理すると、問題の操作は

• の 行目と 行目とを交換する
• の 行目を 行目に (XOR の意味で) 加算する

ができるということになる。これは の各要素を 0, 1 のみの数とみたときの掃き出し法に他ならない。

そして掃き出し法の重要な性質として「掃き出し操作の逆の操作もまた、掃き出し操作である」というのがある。つまり、

• に操作をほどこして にできるか

という問題の代わりに

• にも にも操作をほどこして一致させられるか

という問題を考えても一緒である (この考え方は超頻出のイメージ)。ここで行列の掃き出し法 (行基本変形) には

• 行基本変形を繰り返して得られる行基本変形標準形というのがあり、それは操作の順番に依らずに一意に定まる

という著しい特徴がある (このページの「行列の標準形」の節参照)。よって、 も も行基本変形標準形まで変形して、両者が一致するかを見れば良い。

WA 出しまくった理由

最初は、数列 に操作を繰り返して、数列 の各要素ごとに作れるかどうかをそれぞれ判定して、すべて作れればよいのだと勘違いしていた。

#include <iostream>
#include <vector>
using namespace std;

void Gauss(vector<long long> &A) {
  int rank = 0;
  for (int d = 0; d < 60; ++d) {
    int pivot = -1;
    for (int i = rank; i < (int)A.size(); ++i) {
      if (A[i] & (1LL<<d)) {
        pivot = i;
        break;
      }
    }
    if (pivot == -1) continue;
    swap(A[rank], A[pivot]);
    for (int j = 0; j < (int)A.size(); ++j) {
      if (j == rank) continue;
      if (!(A[j] & (1LL<<d))) continue;
      A[j] ^= A[rank];
    }
    ++rank;
  }
}

int main() {
  int N; cin >> N;
  vector<long long> A(N);
  vector<long long> B(N);
  for (int i = 0; i < N; ++i) cin >> A[i];
  for (int i = 0; i < N; ++i) cin >> B[i];

  Gauss(A);
  Gauss(B);
  if (A == B) puts("Yes");
  else puts("No");
}