P7693 题解

· · 题解

这道题缺少 Special Judge，害得我调了一上午然后发现是没有 Special Judge 的问题

思路

首先可以以 O(n) 的复杂度模拟这个过程，输入中已经提供了每次加入的数（从第 n+1 个数到第 2n 个数）。观察这个过程，可以发现每次加入一个数 x 时，对于这个数加入之前的序列 \{a_1,a_2,...,a_n\}，开关 \{k_1,k_2,...,k_n\} 有：

(\sum_{i=1}^n {a_i \times k_i}) \equiv x \pmod 2

相当于对于每个 a_i=1 的位置，对应的 k_i 之和满足相加后除以 2 的余数为 x。由此可以列出同余方程组，想到利用类似高斯消元的方式解决本题。

然而，多个变量的同余方程组求解并不容易。考虑到相加后对 2 取余等价于做异或运算，问题转变为求解形如下面这样的异或方程组：

\begin{cases} k_1 \operatorname{xor} k_2 \operatorname{xor} k_3 = 1 \\ k_1 \operatorname{xor} k_5 \operatorname{xor} k_6 = 0 \\ \dots \end{cases}

考虑如何对这样的方程组进行消元。类比高斯消元，处理到第 i 行时我们希望第 i+1 行到第 n 行方程均不涉及 k_i。

显然，等号两边同时异或上某个数时，等式仍然成立。因此，对于某个我们希望消去 k_i 的方程，我们可以在其等号两边同时异或上第 i 个方程左侧的式子。例如，对上面的方程组，消去第 2 个方程的 k_1 时可以这样计算：

\begin{aligned} k_1 \operatorname{xor} k_5 \operatorname{xor} k_6 &= 0 \\ k_1 \operatorname{xor} k_5 \operatorname{xor} k_6 \operatorname{xor} k_1 \operatorname{xor} k_2 \operatorname{xor} k_3 &= 0 \operatorname{xor} k_1 \operatorname{xor} k_2 \operatorname{xor} k_3 \\ k_5 \operatorname{xor} k_6 \operatorname{xor} k_2 \operatorname{xor} k_3 &= 0 \operatorname{xor} 1 \end{aligned}

代码实现时，这可以转化为将系数和等号右侧的值都与某行异或。最后统计答案时的方法和高斯消元一致。

注意不要把高斯消元写错。

代码

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

inline void train() {
       ios::sync_with_stdio(false);
       cin.tie(0);
       cout.tie(0);
}

#ifndef ONLINE_JUDGE
#define ONLINE_JUDGE
#endif

constexpr int N = 800, NT = 1504;

int n, mat[N][N], got[N];
bitset<N> gen;
bool vis[N];

inline void swap_mat(int a, int b) {
    if (a == b) return;
    for (int i = 1; i <= n+1; i++) {
        int tmp = mat[a][i];
        mat[a][i] = mat[b][i];
        mat[b][i] = tmp;
    }
}

inline void xor_mat(int target, int source) {
    if (target == source) return;
    for (int i = 1; i <= n+1; i++) {
        mat[target][i] ^= mat[source][i];
    }
}

int main() {

    train();

    cin>>n;
    for (int i = 0; i < n; i++) {
        int x;
        cin>>x;
        if (x) gen.set(i);
    }
    for (int i = 0; i < n; i++) {
        int x;
        cin>>x;

        for (int j = n-1, mpos = 1; j >= 0; j--, mpos++) {
            if (gen.test(j)) mat[i+1][mpos] = 1;
        }
        if (x) mat[i+1][n+1] = 1;

        gen >>= 1;
        if (x) gen.set(n-1);        // Top position
    }
    for (int i = 1; i <= n; i++) {
        int foundrow = -1;
        for (int j = 1; j <= n; j++) {
            if (mat[j][i] && (!vis[j])) {
                foundrow = j;
                break;
            }
        }
        if (foundrow < 0) continue;
        swap_mat(i, foundrow);
        vis[i] = true;
        for (int j = 1; j <= n; j++) {
            if (vis[j]) continue;
            if (mat[j][i]) {
                xor_mat(j, i);
            }
        }
    }
    for (int i = n; i >= 1; i--) {
        int right = mat[i][n+1];
        for (int j = i+1; j <= n; j++) {
            right ^= got[j] & mat[i][j];
        }
        if (mat[i][i] == 0) {
            if (right == 1) {
                cout<<"-1"<<endl;
                return 0;
            } else {
//              got[i] = 1;                         // 加不加都可以，没有 spj 时分数不同 
            }
        } else {
            got[i] = right;
        }
    }
    for (int i = 1; i <= n; i++) cout<<got[i]<<' ';
    cout<<endl;

    return 0;
}