UOJ Logo Universal Online Judge

UOJ

#549. 【UNR #4】序列妙妙值

附件下载 统计

出题人 01 很喜欢加法,也很喜欢异或运算(即 C/C++ 里的 ^ 运算符)。有天他一拍脑袋:把两个运算混一起,岂不是妙极了?

对于一个序列 $b_1, \dots, b_m$,他希望你将序列 $b$ 划分为 $k$ 段连续非空子序列,使得每一段的异或和之和最小。即,他想知道在所有满足 $0 = p_0 < p_1 < \cdots < p_k = m$ 条件的序列 $p$ 中下式的最小值: $$ \sum_{i=1}^{k} (b_{p_{i-1} + 1} \mathbin{\mathrm{xor}} \cdots \mathbin{\mathrm{xor}} b_{p_i}) $$ 这个最小值即称为这个序列的妙妙值

但是这个问题非常简单,于是出题人 01 找来了一个长度恰好为 $n$ 的非负整数序列 $a_1, \dots, a_n$。他想考考你,$a$ 的每个前缀 $a_1, \dots, a_j$ ($k \le j \le n$)的妙妙值分别是多少呢?

输入格式

第一行两个正整数 $n,k$,含义同题面。

接下来一行 $n$ 个非负整数,第 $i$ 个非负整数表示 $a_i$。

输出格式

第一行 $n-k+1$ 个整数,分别表示前 $j = k, k+1, \dots, n$ 个元素组成的序列的妙妙值。

样例一

input

6 2
1 1 4 5 1 4

output

2 4 1 0 4

explanation

对于序列 $a_1, \dots, a_6$,可以将序列划分为 $a_1, a_2$ 和 $a_3, a_4, a_5, a_6$ 两段。

此时答案为 $(1 \mathbin{\mathrm{xor}} 1)+(4 \mathbin{\mathrm{xor}} 5 \mathbin{\mathrm{xor}} 1 \mathbin{\mathrm{xor}} 4)=0+4=4$。

注意 $a_1, a_2, a_3, a_4, a_5$ 和 $a_6$ 也是一种合法的划分方案。

样例二

见下发文件。

数据范围同测试点 3 ~ 4。

限制与约定

测试点编号$n$特殊性质
1 ~ 2 $\le 15$
3 ~ 4 $\le 5000$
5 ~ 6 $\le 60000$ $a_i \lt 2^8$
7 ~ 8 $a_i \lt 2^{12}$
9 ~ 10

对于所有测试点,满足 $1 \le k \le n \le 60000, k \le 8,a_i < 2^{16}$

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载