Switches

2020-2021 ACM-ICPC, Asia Seoul Regional Contest

J. Switches

题目链接

题目模型：

给定一个有 n n n 个二进制长度为 1-500 数字的集合，我们希望能够找到 n n n 个子集，这 n n n 个子集中的数字两两异或可以分别得到 2 n − 1 , 2 n − 2 , . . . , 2 0 2^{n-1}, 2^{n-2}, ..., 2^{0} 2n−1,2n−2,...,20。让我们按顺序输出这 n n n 个子集。当然，如果不存在答案输出-1

题目分析下来也就是线性基能否异或得到某个数，板子题。唯一不同的就是二进制数过大不能直接异或，需要数组手动异或。另外需要记录得到每个向量需要的原向量标号。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -f; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
const int maxN = 505;
const int maxBit = 505;
int n;
int mp[maxN][maxN];
int p[maxBit][maxN]; //基向量
vector<int> vt[maxBit]; //记录每个基向量是由哪几个向量异或得到的
void add(int x) { //将mp[x]插入
    int tnum[n + 1];
    memset(tnum, 0, sizeof(tnum));
    tnum[x + 1] = 1;
    for(int i = 0; i < n; ++ i ) {
        if(mp[x][i]) {
            if(vt[i].empty()) {
                //p[i] = mp[x]
                for(int j = 0; j < n; ++ j ) p[i][j] = mp[x][j];
                for(int j = 1; j <= n; ++ j ) if(tnum[j]) vt[i].push_back(j);
                break;
            }
            //mp[x]异或p[i]
            for(int j = i; j < n; ++ j ) mp[x][j] ^= p[i][j];
            int siz = vt[i].size();
            for(int j = 0; j < siz; ++ j ) {
                tnum[vt[i][j]] ^= 1;
            }
        }
    }
}

int tar[maxBit];
vector<int>ans[maxN];
bool Zero(int i) {
    int ans = 0;
    for(; i < n; ++ i) {
        ans += tar[i];
    }
    return ans == 0;
}
bool judge(int x) { //判断tar能不能由线性基得到
    int tnum[n + 1];
    memset(tnum, 0, sizeof(tnum));
    for(int i = 0; i < n; ++ i ) {
        if(tar[i]) {
            //tar异或p[i]
            for(int j = i; j <= n; ++ j ) tar[j] ^= p[i][j];
            int siz = vt[i].size();
            for(int j = 0; j < siz; ++ j ) {
                tnum[vt[i][j]] ^= 1;
            }
            if(Zero(i)) {
                for(int j = 1; j <= n; ++ j ) if(tnum[j]) ans[x].push_back(j);
                return true;
            }
        }
    }
    return false;
}
int main() {
    n = read();
    for(int i = 0; i < n; ++ i ) {
        for(int j = 0; j < n; ++ j ) {
            mp[i][j] = read();
        }
        add(i);
    }
    bool ok = true;
    for(int i = 0; i < n; ++ i ) {
        tar[i] = 1;
        if(i) tar[i - 1] = 0;
        if(!judge(i)) {
            ok = false;
            break;
        }
    }
    if(!ok) {
        puts("-1");
    } else {
        for(int i = 0; i < n; ++ i ) {
            int siz = ans[i].size();
            for(int j = 0; j < siz; ++ j ) {
                printf("%d ", ans[i][j]);
            }
            puts("");
        }
    }
    return 0;
}