F. Unusual Matrix

たしかにそうっぽいが天才感がある。もっと再現性のある方法はないか?ということで以下に続く

  • 私の解法
    • A[i][j] ^= B[i][j]として、Aを全て0にする問題にする
    • 1行目のswapを「やる」「やらない」の両方試す
    • 1行目のswapをやった後でも1行目にまだ1が残っているならば、その1は縦swapにより0にする必要がある。つまり1行目を決めてやると縦のswapをするかどうかが全て決まる
    • あと残された操作は2行目以降の横swapのみ。これを使って全てを0にできればYES
    • (蟻本でも「1行目を決めてやれば後は決まる」というのがありましたね)

code

// for codeforces
void solve(){
  ll N;
  cin>>N;
  VV A(N, VI(N));
  VV B(N, VI(N));
  rep(i,N){
    string s;cin>>s;
    rep(j,N){
      if(s[j]=='1')A[i][j]=1;
    }
  }
  rep(i,N){
    string s;cin>>s;
    rep(j,N){
      if(s[j]=='1')B[i][j]=1;
    }
  }
  rep(i,N){
    rep(j,N){
      A[i][j] ^= B[i][j];
    }
  }
  
  auto A_original = A;
  // 1週目 1行目をswapしない場合
  // 2週目 1行目をswapした場合
  rep(_,2){
    A = A_original;

    if(_==0){
      // 1行目をswap
      rep(i,N){
        A[0][i] ^= 1;
      }
    }

    // check
    // 1行目を見て、列のswapが必要な箇所は今1である部分
    rep(x,N){
      if(A[0][x]==1){
        // その列は全てswapする
        rep(y,N){
          A[y][x] ^= 1;
        }
      }
    }

    bool ok=true;
    FOR(y,1,N){
      // 残りの行は0にできるか
      // 全部0か、全部1なら横swapにより可能
      ll sum = SUM(A[y]);
      if(sum==0 or sum==N){
        // safe
      }else{
        ok=false;
      }
    }
    if(ok){
      p_yes();return;
    }
  }
  p_no();
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;cin>>N;
    while(N--)solve();
    
    return 0;
}