题目描述

难度分:$2600$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 10^4$。

每组数据输入$n(1 \leq n \leq 10^4)$和长为$n$的数组$a(0 \leq a[i] \lt 2^{60})$。

不断执行如下操作，直到$a$中只有一个元素：把$a$分成左右两段，丢弃其中异或和小的那段。如果两段异或和相同，丢弃哪个都可以。

对于每个$a[i]$，回答：最终剩下的数能否是$a[i]$？输出一个长为$n$的01字符串，其中第$i$个字符表示$a[i]$的答案（$0$表示不能，$1$表示能）。

输入样例

6
6
3 2 1 3 7 4
5
1 1 1 1 1
10
1 2 4 8 4 1 2 3 4 5
5
0 0 0 0 0
5
1 2 3 0 1
1
100500

输出样例

111111
10101
0001000000
11111
11001
1

算法

动态规划

状态定义

看着像是区间DP，$f[i][j]$表示子数组$[i,j]$是否能够保留下来。在这个定义下，答案就应该是$f[i][j]$（$i \in [1,n]$）。

状态转移

从大区间转移到小区间，对于某个区间$[l,r]$，考虑把$[l,r]$分成两段的分割点$k$，它能将$[l,r]$分割为$[l,k]$和$(k,r]$两个子数组。预处理出一个前缀异或和数组$s$，枚举$k$的时候比较这两段的区间异或和，判断哪一段可以留下来。

但是这样经典的区间DP状态转移是$O(n)$的，整体的时间复杂度通常都为$O(n^3)$，在本题$n \leq 10^4$的数据规模下根本行不通。我们考虑如何优化转移，设$s_{l,r}$为子数组$[l,r]$的异或和。考虑区间$[l,k]$什么时候可以从区间$[l,r]$转移过来（$l \leq k \lt r$），分为两种情况：

1. 如果$s_{l,r}$的第$x$位为$0$，不论$s_{l,k}$这一位取什么值都会与另外一半相等（如果是$1$，另一半这一位也必须是$1$才能使得$s_{l,r}$这一位是$0$；如果是$0$，另一半这一位也必须是$0$才能使得$s_{l,r}$这一位是$0$）。
2. 如果$s_{l,r}$这一位是$1$，必须在这是最高位的情况下才要求$s_{l,k}$这一位也是$1$。不然因为$s_{l,k}$前面已经比另一半大了，这一位取值将不再有限制。

因此，只有$s_{l,k}$在$highbit(s_{l,r})$位上是$1$时（$highbit(x)$表示$x$最高位的$1$，与$lowbit$相对应），$[l,r]$才能成为$[l,k]$的转移来源。

最后就是老套路了，外层倒序（先枚举大区间再枚举小区间）循环枚举区间长度$len$，然后内层循环枚举区间左端点$l$，右端点为$r=l+len-1$。由$s_{l,r}=s_{l,k} \oplus s_{k+1,r}$，易知$highbit(s_{l,r})=max(highbit(s_{l,k}),higbit(s_{k+1,r}))$。

如果$[l,k]$可以被保留，只能是$highbit(s_{l,k})=higbit(s_{l,r})$。$L[i]$表示以$i$为左端点的所有区间异或值的最高位，每遇到一个新的可行区间$[i,j]$，就把$highbit(s_{i,j})$异或到$L[i]$上。同理，$R[j]$表示以$j$为右端点的所有区间异或值的最高位，每遇到一个新的可行区间$[i,j]$，就把$highbit(s_{i,j})$异或到$R[j]$上。这样的话，每次只要$L[i] \land s_{i,j}$或者$R[j] \land s_{i,j}$不为$0$，就说明区间$[i,j]$是个可行区间。这是因为区间长度是从大到小枚举的，此时$L$和$R$中存储的是比$[i,j]$更大的区间信息，说明在某个端点重合的大区间中，可以保留住区间$[i,j]$。

复杂度分析

时间复杂度

状态数量是$O(n^2)$级别（但是并不需要把$dp$数组$f$的空间开出来），单次转移是$O(1)$，因此整个算法的时间复杂度为$O(n^2)$。

空间复杂度

前缀异或和数组$s$的空间为$O(n)$；$L$数组和$R$数组的空间也是$O(n)$；而由于不是有顺序的线性DP，需要构建一个答案数组，空间也是$O(n)$的。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 1e4 + 5;
int T, n;
LL a[N], s[N], L[N], R[N], ans[N];

// 最高位的1，对应lowbit
LL highbit(LL x) {
    return x != (1ll<<62)? (1ull<<(63 - __builtin_clzll(x))): 1ll<<62;
}

// 区间异或和
LL sum(int l, int r) {
    return (s[r]^s[l - 1])? (s[r]^s[l - 1]): 1ll<<62;
}

signed main(){
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            L[i] = R[i] = 0;
        }
        for(int i = 1; i <= n; i++) {
            s[i] = s[i - 1] ^ a[i];
        }
        L[1] |= highbit(sum(1, n));
        R[n] |= highbit(sum(1, n));
        ans[1] = 1;
        for(int len = n - 1; len >= 1; len--) {
            for(int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                LL flag = (((sum(i, j)|(1ll<<62))&L[i])|((sum(i, j)|(1ll<<62))&R[j]));
                if(flag) {
                    // [i,j]是可保留的区间
                    L[i] |= highbit(sum(i, j));
                    R[j] |= highbit(sum(i, j));
                }
                if(len == 1) {
                    ans[i] = flag > 0;   // 区间长度为1时计算答案
                }
            }
        }
        for(int i = 1; i <= n; i++) {
            printf("%lld", ans[i]);
        }
        puts("");
    }
    return 0;
}