CF1863F.Divide, XOR, and Conquer
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given an array of n integers a1,a2,…,an .
In one operation you split the array into two parts: a non-empty prefix and a non-empty suffix. The value of each part is the bitwise XOR of all elements in it. Next, discard the part with the smaller value. If both parts have equal values, you can choose which one to discard. Replace the array with the remaining part.
The operations are being performed until the length of the array becomes 1 . For each i ( 1≤i≤n ), determine whether it is possible to achieve the state when only the i -th element (with respect to the original numbering) remains.
Formally, you have two numbers l and r , initially l=1 and r=n . The current state of the array is [al,al+1,…,ar] .
As long as l<r , you apply the following operation:
- Choose an arbitrary k from the set {l,l+1,…,r−1} . Denote x=al⊕al+1⊕…⊕ak and y=ak+1⊕ak+2⊕…⊕ar , where ⊕ denotes the bitwise XOR operation.
- If x<y , set l=k+1 .
- If x>y , set r=k .
- If x=y , either set l=k+1 , or set r=k .
For each i ( 1≤i≤n ), determine whether it is possible to achieve l=r=i .
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤10000 ). The description of the test cases follows.
The first line of each test case contains one integer n ( 1≤n≤10000 ).
The second line of each test case contains n integers a1,a2,…,an ( 0≤ai<260 ).
It is guaranteed that the sum of n over all test cases does not exceed 10000 .
输出格式
For each test case, output a single string of length n where the i -th element is equal to 1 if it is possible to achieve l=r=i and is equal to 0 otherwise.
输入输出样例
输入#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
输出#1
111111 10101 0001000000 11111 11001 1
说明/提示
In the first test case, it is possible to achieve l=r=i for any i from 1 to n :
- for i=1 : [1;6]→[1;4]→[1;1] ;
- for i=2 : [1;6]→[1;3]→[2;3]→[2;2] ;
- for i=3 : [1;6]→[1;3]→[3;3] ;
- for i=4 : [1;6]→[1;4]→[4;4] ;
- for i=5 : [1;6]→[5;6]→[5;5] ;
- for i=6 : [1;6]→[6;6] .
Let's take a closer look at i=2 . Initially l=1 , r=6 .
- We can choose k=3 and set r=k=3 since (3⊕2⊕1)=0≥0=(3⊕7⊕4) ;
- Next, we can choose k=1 and set l=k+1=2 since 3≤3=(2⊕1) ;
- Finally, we can choose k=2 and set r=k=2 since 2≥1 .