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;
}