P17129 [ICPC 2025 Shanghai R] Round screws

试题来自 [清华大学学生算法协会](https://gitlink.org.cn/thusaa/ICPC2025shanghai)。

NIT 喜欢圆形的螺丝。他也喜欢 $\oplus$ 运算符，因为它让他想起圆形的螺丝。这里 $\oplus$ 表示按位异或运算。 定义一个序列 $a_1, a_2, \cdots, a_n$ 的价值 $V_a$ 为 $V_a = a_1 + a_n + \sum_{i=1}^{n-1} (a_i \oplus a_{i+1})$。 给定一个序列 $a_1, a_2, \cdots, a_n$，你可以执行任意次如下操作： - 选择一个下标 $i$ ($1 \le i \le n$)，将 $a_i$ 改为任意非负整数；该操作的花费为 $C$。 请最小化序列的价值与操作花费之和。换言之，设 $p$ 为你执行的操作次数，$V_{a'}$ 为操作后序列 $a$ 的价值，你需要最小化 $pC + V_{a'}$。

输入包含多组测试用例。第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。 对于每组测试用例，第一行包含两个整数 $n, C$ ($2 \le n \le 10^5, 0 \le C < 2^{19}$)，分别表示序列长度和一次操作的花费。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{18}$)，表示序列中的元素。 保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

对于每组测试用例，输出一行一个整数，即 $pC + V_{a'}$ 可能的最小值。

对于第 $1$ 组测试用例，一种达到最小值的方式是将序列变为 $[1, \textbf{1}, \textbf{1}, \textbf{0}]$；加粗的数字是被修改过的。最终序列的价值为 $2$，共执行了 $3$ 次操作；总价值 $+$ 花费为 $2 + 3 \times 4 = 14$。 对于第 $2$ 组测试用例，一种达到最小值的方式是将序列变为 $[6, 6, 6, \textbf{6}, \textbf{6}, 6, 6, 6]$；最终价值为 $12 + 2 \times 6 = 24$。 翻译由 DeepSeek V4 Pro 完成