首先有一个 \(naive\) 的做法。
直接 \(O(n^3)\) 暴力判断。
考虑寻找突破口。
假如给了你一个序列，异或值为 \(S\) ，那么实际上假如中间有一个断点 \(mid\) ，那么我们最终决定保留哪一段，实际上是看 \(S\) 的最高位 \(1\) 的位置来比较的，所以我们只需要管最高位的 \(1\) 就可以了。（因为如果为 \(0\) 就是要么都是 \(1\) ，要么都是 \(0\) ）
所以我们只需要关注最高位即可。
我们记一个 \(L_i,R_i\) 分别表示以 \(i\) 开始时，这一段序列要想成功，可以有的异或值有哪些（只要有其中一位，就能成功），而 \(R\) 就是以他结束，同理。
然后如果一个区间可行，记他的最高位为 \(k\) ，那么他左端点的 \(L\) 或上 \(1<<k\) ，右端点 \(R\) 或上 \(1<<k\) 。
不过如果异或值为 \(0\) 就要特判，因为这时候 \(l,r\) 不管是什么都可以。
因为你从中间截断，一定会有 \(x^y=S=0\) 所以 \(x=y\) ，所以从里面随便选择一个就可以了。
总时间复杂度 \(O(n^2)\)
启示：
如果有 \(x^y=S\) ，然后让你比较 \(x,y\) 的大小，直接看 \(S\) 最高位的 \(1\) 即可。
点击查看代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAXN=10010;
LL T;
LL n,b[MAXN],s[MAXN],L[MAXN],R[MAXN];
bool dp[MAXN][MAXN];
int main () {
scanf("%lld",&T);
while(T--) {
scanf("%lld",&n);
for(int i=1;i<=n;++i) {
scanf("%lld",&b[i]);
s[i]=s[i-1]^b[i];
L[i]=R[i]=0;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) dp[i][j]=0;
dp[1][n]=1;
for(int i=n;i>=1;--i) {
int RR=n-i+1;
for(int j=1;j<=RR;++j) {
int r=j+i-1;
LL ls=s[r]^s[j-1];
if(L[j]==-1||(ls&L[j])) dp[j][r]=1;
if(R[r]==-1||(ls&R[r])) dp[j][r]=1;
if(!dp[j][r]) continue;
if(!ls) {
L[j]=R[r]=-1;
continue;
}
LL uu=63-__builtin_clzll(ls);
L[j]|=(1ll<<uu);
R[r]|=(1ll<<uu);
}
}
for(int i=1;i<=n;++i) printf("%d",dp[i][i]);
puts("");
}
return 0;
}