题解归档 - cf406A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf406A
• 本地来源：problems/cf406A/idea.md
• 题目链接：https://codeforces.com/contest/406/problem/A
• 原始标题：cf406A - Unusual Product

思路

cf406A - Unusual Product

sum_i dot(row_i, col_i) = sum_i sum_j a[i][j] a[j][i] in GF(2).

For i != j, pair (i,j) and (j,i) contributes twice the same product, so it cancels modulo 2. For i == j, contribution is a[i][i]^2 = a[i][i]. Therefore the answer is exactly xor/parity of the main diagonal.

Row flip i and column flip i both flip only one diagonal bit a[i][i] among the surviving terms, so the maintained answer toggles for every query of type 1 or 2.

代码

来源：problems/cf406A/solution.cpp

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1, x; j <= n; j++) {
            cin >> x;
            if (i == j) ans ^= x;
        }
    }
    int q;
    cin >> q;
    string out;
    out.reserve(q);
    while (q--) {
        int op;
        cin >> op;
        if (op == 3) {
            out.push_back(char('0' + ans));
        } else {
            int x;
            cin >> x;
            ans ^= 1;
        }
    }
    cout << out << '\n';
    return 0;
}