You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

人生是艰难的，但是小花决定把一道不是那么艰难的问题放在第二题。

小花会给你一个长为 $n$ 的序列 $\{a\}$ 和一个正整数 $m$。定义一段区间的“艰难值” $h(l,r)$ 如下：

$$h(l,r) = \sum_{l\leq x\leq y\leq r} \{a_{x} \operatorname{xor} a_{x+1} \operatorname{xor} a_{x+2}\cdots \operatorname{xor} a_y = m\}_{0~\mathrm{or}~1}$$

其中 $\operatorname{xor}$ 为异或运算，$\{t\}_{0~\mathrm{or}~1}=1$ 当且仅当 $t$ 为真，其余情况下均为 $0$。

现在小花需要让你将 $\{a\}$ 划分为互不相交的恰好 $p$ 个连续段，且这些段的并等于 $\{a\}$ 。Ta 想知道，所有划分方案中，全部连续段的艰难值之和最小是多少？

形式化的讲，你需要确定一系列不交且并为 $[1,n]$ 的恰好 $p$ 个区间 $[l_i,r_i]$ 使得

$$\sum_{i=1}^p h(l_i,r_i)$$

最小。

输入格式

第一行共 $3$ 个正整数 $n, p, m$，含义见题目描述。

接下来一行共 $n$ 个整数描述序列 $\{a\}$。

输出格式

输出一行共 $1$ 个整数，表示所有划分方案中艰难值之和的最小值。

样例

10 2 3
2 3 3 2 1 0 1 3 9 6

4

输入数据2

见样例文件 ex1.in。

输出数据2

见样例文件 ex1.out。

输入数据3

见样例文件 ex2.in。

输出数据3

见样例文件 ex2.out。

数据范围与约束

对于前 $20\%$ 的数据，满足 $1\leq n\leq 500$。

对于前 $40\%$ 的数据，满足 $1\leq n\leq 5000$，$1\leq p\leq 8$。

对于前 $60\%$ 的数据，满足 $1\leq n\leq 3\times 10^4$，$1\leq p\leq 12$，$0\leq a_i,m \leq 2\times 10^5$ 。

另有 $10\%$ 的数据，满足 $m = 0$ 。

对于全部 $100\%$ 的数据，满足 $1 \leq n \leq 2\times 10^5$，$1 \leq p \leq 20$，$0\leq a_i,m\leq 10^6$。