最近学了一点线性基……所以也就做了一些线性基的题目

这题还算挺简单的吧……先转成求第$s - k + 1$（这里用$s$表示异或和有多少种）大。求出线性基，然后从高位向低位枚举，然后乱搞就行……

唯一的坑就是子集要求非空。这样有可能会出现选不出$0$的情况，但是稍微思索一下可以发现如果$|B| < n$（这里用$B$表示线性基）那么一定可以用$B$里的东西凑出来一个数，然后再和不在线性基里的一个数异或一下，这样就能搞出来$0$了。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
using ll = long long int;
const int maxb = 51;
ll T[maxb];
void insert(ll x) {
  for(int i = 50; i >= 0; i --) {
    if(!x) break;
    if((x & (1LL << i)) == 0) continue;
    if(T[i]) {
      x ^= T[i];
    } else {
      for(int j = i - 1; j >= 0; j --) {
        if(x & (1LL << j)) {
          x ^= T[j];
        }
      }
      for(int j = i + 1; j < maxb; j ++) {
        if(T[j] & (1LL << i)) {
          T[j] ^= x;
        }
      }
      T[i] = x; break;
    }
  }
}

#ifdef LOCAL
#define LO "%I64d"
#else
#define LO "%lld"
#endif
int main() {
  int sz = 0;
  ll tot = 0;
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    ll x; scanf(LO, &x);
    insert(x);
  }
  for(int i = 0; i < maxb; i ++) if(T[i]) sz ++;
  tot = (1LL << sz) - 1LL;
  if(sz < n) tot ++;
  int m; scanf("%d", &m);
  while(m --) {
    ll k; scanf(LO, &k);
    if(k <= 0LL || k > tot) {
      puts("-1");
    } else if(sz < n && k == 1LL) {
      puts("0");
    } else {
      k = tot - k + 1LL;
      int rest = sz; ll ret = 0;
      for(int i = 50; i >= 0; i --) {
        if(!T[i]) continue;
        rest --;
        if(k <= (1LL << rest)) {
          ret ^= T[i];
        } else {
          k -= (1LL << rest);
        }
      }
      printf(LO, ret); puts("");
    }
  }
  return 0;
}

• 相关文章
• 全局相关文章