【题解】kth异或和/魔改版线性基

【题解】魔改版线性基

魔改版线性基解决此类问题。

联系线性空间的性质，我们直接可以构造出这样的基：

\[100000
\\
010000
\\
000010
\\
000001
\]

使得每个基的最高位是唯一的，我们的目的是要能够保证从上往下一直异或一直变大，所以不能使基出现这样的情况:

\[100001
\\
000001
\]

考虑如何构造\(kth\) 大(小)，考虑这样的性质，我们记\(a_i\)表示从下往上第\(i\)个基，显然从\(0\)开始，如果我们异或了\(a_x\)，那么我们可以保证我们会比这个线性空间内\(2^{x-1}\)个值都要大，直接考虑从上往下查询，类似树上倍增。

考虑无解的情况，显然当我们发现\(k \ge 2^{|E|}\)时就无解了。

然而我们有一个问题，那就是我们默认\(0\)是可以被表示出来的，然而我们知道，当给定元素全部互为不相关时，这个时候就不存在一个\(0\)会被表示出来了。那么我们可以特判一下即可 。

好，那么如何构造从上往下一直异或一直变大的基呢？魔改一下就好了。具体看代码。

分析复杂度：我们把魔改操作的\(log^2\)看做常数吧...那就是\(O(nlogn)\)

当然你如果不承认魔改操作是常数，那就继续魔改\(upd\)函数，也可以做到\(nlogn\)。具体就是加入的时候从小往大加。

下面的第\(k\)小，转换为第\(k\)大用\(2^{|E|}​\)减去即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

template <class ccf>

inline ccf qr(ccf ret) {

      ret = 0;

      register char c = getchar();

      while (c < 48 || c > 57) c = getchar();

      while (c >= 48 && c <= 57) ret = ret * 10 + c - 48, c = getchar();

      return ret;

}

namespace bs {

      ll num[51], sav[51];

      struct BASE {

	    ll data[51];

	    int cnt;

	    ll p;

	    BASE() {

		  memset(data, 0, sizeof data);

		  cnt = 0;

		  p = 1;

	    }

	    inline ll size() { return 1LL << cnt; }

	    inline void set() {

		  for (register int t = 1; t <= 50; ++t)

			if (data[t])

			      for (register int i = t + 1; i <= 50; ++i)

				    if (data[i] & num[t])

					  data[i] ^= data[t];

	    }

	    inline void upd(ll x) {

		  for (register int t = 50; t >= 1; --t) {

			if (x & num[t]) {

			      if (not data[t]) {

				    data[t] = x;

				    ++cnt;

				    break;

			      } else

				    x ^= data[t];

			}

			if(not x) {

			      p=0;

			      break;

			}

		  }

	    }

	    inline ll que(ll k) {

		  register ll ret = 0, sav = 0;

		  if(cnt==50) --k;

		  if (k > this->size())

			return -1;

		  for (register int t = 50, f = 0; t >= 1; --t) {

			if (data[t]) {

			      ++f;

			      if (sav + (1LL << (cnt - f)) <= k)

				    sav += 1LL << (cnt - f), ret = ret ^ data[t];

			}

		  }

		  return ret;

	    }

	    inline void clear() {

		  memset(data, 0, sizeof data);

		  cnt = 0;

	    }

	    inline void debug() {

		  for (register int t = 50; t >= 1; --t) {

			if (data[t])

			      cout << ((bitset<10>)data[t]) << ' ' << data[t] << endl;

		  }

		  cout << endl;

	    }

      };

      inline void init() {

	    for (num[0] = 2, num[1] = 1; num[0] <= 50; ++num[0]) num[num[0]] = num[num[0] - 1] << 1;

      }

}

bs::BASE qaq;

int main() {

      bs::init();

      int n = qr(1);

      for (register int t = 1; t <= n; ++t) qaq.upd(qr(1ll));

      int m = qr(1);

      qaq.set();

      for (register int t = 1; t <= m; ++t) printf("%lld\n", qaq.que(qr(1ll)));

      return 0;

}