Codeforces 1863F Divide, XOR, and Conquer

记 \(s_{l, r} = \oplus_{i = l}^r a_i\)。

考虑到这个相当于是 \([l, r]\) 内分裂区间，可以考虑区间 \(\text{DP}\)。
即记 \(f_{l, r}\) 为 \([l, r]\) 区间是否能被遍历到。

转移考虑对于 \([l, r]\)，考虑在已知的条件下（\(len\ge r - l + 1\)）\([l, r]\) 是否合法。
即到这个状态时再从之前的状态算过来。

考虑到因为拆分区间 \(l, r\) 肯定不动。
假设 \(l\) 不动，那么就相当于是 \([l, R]\to [l, r](R > r)\)，不妨就考虑由 \(s_{l, r}\) 和 \(s_{l, R}\) 来判断 \([l, R]\) 能否遍历到 \([l, r]\)。
那么有 \(s_{r + 1, R} = s_{l, r}\oplus s_{l, R}\)。

1. 首先若 \(s_{l, R} = 0\)，那么肯定有 \(s_{r + 1, R} = s_{l, r}\)，那么 \([l, r]\) 肯定能被遍历到。
2. 否则考虑令 \(w = \operatorname{highbit}(s_{l, R})\)，那么因为 \(> w\) 位 \(s_{l, R}\) 都为 \(0\)，那么这些位 \(s_{l, r}\) 和 \(s_{r + 1, R}\) 肯定都是相同的，然后到了第 \(w\) 位，因为在这一位 \(s_{l, R}\) 为 \(1\)，那么这一位 \(s_{l, r}\) 和 \(s_{r + 1, R}\) 肯定不同。
   所以说在第 \(w\) 位若 \(s_{l, r}\) 为 \(1\) 那么 \([l, r]\) 就能被遍历到。

发现这些信息都只需要在左端点和右端点的时候维护。
对于第一种情况，只需要记录对应端点存不存在合法且异或和 \(= 0\) 的区间。
对于第二种情况，例如左端点 \(l\)，记录一个 \(g_{l, w}\) 为是否存在 \([l, r]\) 满足 \([l, r]\) 合法且 \(\operatorname{highbit}(s_{l, r}) = w\)。
那么判断的时候就相当于是询问是否存在位 \(i\) 使得 \(g_{l, i} = 1\) 且 \(s_{l, r}\) 第 \(i\) 位为 \(1\)。
那么这个就相当于是取交集，就可以用 \(\operatorname{bitand}\) 来快速算。

时间复杂度 \(\mathcal{O}(n^2)\)。

#include<bits/stdc++.h>
using ull = unsigned long long;
const int maxn = 1e4 + 10;
ull a[maxn];
ull fl[maxn], fr[maxn];
int fl0[maxn], fr0[maxn];
inline void Main() {
   int n;
   scanf("%d", &n);
   for (int i = 1; i <= n; i++)
      scanf("%llu", &a[i]), a[i] ^= a[i - 1];
   for (int i = 1; i <= n; i++)
      fl[i] = fr[i] = 0, fl0[i] = fr0[i] = 0;
   for (int len = n; len; len--)
      for (int l = 1, r = len; r <= n; l++, r++) {
         ull v = a[r] ^ a[l - 1];
         int f = len == n || ((v & fl[l]) > 0) || ((v & fr[r]) > 0) || fl0[l] || fr0[r];
         if (l == r) printf("%d", f);
         if (f) {
            if (! v)
               fl0[l] = fr0[r] = 1;
            else
               fl[l] |= 1ull << std::__lg(v), fr[r] |= 1ull << std::__lg(v);
         }
      }
   puts("");
}
int main() {
   int T;
   scanf("%d", &T);
   while (T--)
      Main();
   return 0;
}