小花认为人生艰难
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
人生是艰难的,但是小花决定把一道不是那么艰难的问题放在第二题。
小花会给你一个长为 的序列 和一个正整数 。定义一段区间的“艰难值” 如下:
$$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} $$其中 为异或运算, 当且仅当 为真,其余情况下均为 。
现在小花需要让你将 划分为互不相交的恰好 个连续段,且这些段的并等于 。Ta 想知道,所有划分方案中,全部连续段的艰难值之和最小是多少?
形式化的讲,你需要确定一系列不交且并为 的恰好 个区间 使得
最小。
Format
Input
第一行共 个正整数 ,含义见题目描述。
接下来一行共 个整数描述序列 。
Output
输出一行共 个整数,表示所有划分方案中艰难值之和的最小值。
Samples
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。
Constraints
对于前 的数据,满足 。
对于前 的数据,满足 ,。
对于前 的数据,满足 ,, 。
另有 的数据,满足 。
对于全部 的数据,满足 ,,。