#P13774. CF1863F Divide, XOR, and Conquer

    ID: 12970 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-区间 DP异或前缀和提取最高置位位集求交位集求并

CF1863F Divide, XOR, and Conquer

题目

给定一个长度为 nn 的整数数组 a1,a2,…,ana_1,a_2,\ldots,a_n。

一次操作中,你把当前数组分成两段:非空前缀和非空后缀。两段的“价值”分别等于各自所有元素的按位异或(XOR)值。然后:

  • 丢弃价值较小的那一段;
  • 若两段价值相等,则你可以任选丢弃其中一段;
  • 用剩下的那一段替换当前数组。

不断重复操作,直到数组长度变为 11。

对每个 i (1≤i≤n)i\ (1\le i\le n),判断是否存在一种操作序列,使得最终只剩下原数组中的第 ii 个元素。

更形式化地:维护两个指针 l,rl,r,初始 l=1,r=nl=1,r=n,当前数组为 [al,al+1,…,ar][a_l,a_{l+1},\ldots,a_r]。当 l<rl<r 时执行:

  • 任选 k∈l,l+1,…,r−1k\in{l,l+1,\ldots,r-1};
  • 令$$x=a_l\oplus a_{l+1}\oplus\cdots\oplus a_k,\qquad y=a_{k+1}\oplus a_{k+2}\oplus\cdots\oplus a_r$$
  • 若 x<yx<y,令 l=k+1l=k+1;
  • 若 x>yx>y,令 r=kr=k;
  • 若 x=yx=y,可任选令 l=k+1l=k+1 或 r=kr=k。

对每个 ii,判断是否可能达到 l=r=il=r=i。

输入格式

多组测试。

  • 第一行一个整数 tt,表示测试组数。

  • 接下来 tt 组测试,每组:

    • 第一行一个整数 nn;
    • 第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

对每组测试,输出一个长度为 nn 的 01 串:第 ii 位为 1 表示可以最终只剩下第 ii 个元素,否则为 0。

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

约束

  • 1≤t≤1041\le t\le 10^4
  • 1≤n≤1041\le n\le 10^4
  • 0≤ai<2600\le a_i<2^{60}
  • 所有测试的 nn 之和不超过 10410^4

部分分

子任务编号 额外限制(在原约束基础上) 分值
1 所有测试满足 n=1n=1 5
2 所有测试满足 n≤50n\le 50 10
3 所有测试满足 n≤2000n\le 2000 15
4 所有测试满足 ai<210a_i<2^{10} 10
5 所有测试满足 ai<220a_i<2^{20} 15
6 每个测试中,数组是 0,1,…,n−10,1,\ldots,n-1 的一个排列 10
7 无额外限制(原题完整约束) 35
合计 100

说明:所有数据文件都满足“每个文件内所有测试的 ∑n≤10000\sum n\le 10000”。