← 返回题目列表

Codeforces · 2137/E

E. 墨西哥化

中文机器翻译题面 查看原题

给定一个大小为 $$$n$$$ 的数组 $$$a$$$ 和一个整数 $$$k$$$。您执行以下过程 $$$k$$$ 次:

  • 对于每个元素 $$$a_i$$$,将 $$$a_i$$$ 设置为 $$$\operatorname{mex}$$$$$$^{\text{∗}}$$$$$$(a_1,a_2,\ldots,a_{i-1},a_{i+1},a_{i+2}, \ldots,a_n)$$$。换句话说,您将 $$$a_i$$$ 设置为数组中所有其他元素的 $$$\operatorname{mex}$$$。 这是同时对数组中的所有元素执行的操作。

请求所有 $$$k$$$ 操作后数组中元素的总和。

$$$^{\text{*}}$$$整数集合 $$$d_1, d_2, \ldots, d_k$$$ 的最小排除 (MEX) 被定义为集合 $$$d$$$ 中不出现的最小非负整数 $$$x$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n \leq 2\cdot 10^5, 1 \leq k \leq 10^9$$$) – $$$a$$$ 中的元素数量和完成的操作数量。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i \leq n$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,在新行上输出所有 $$$k$$$ 操作后的元素总和。

示例

输入
复制

5
3 3
0 2 1
2 4
0 2
4 1
0 0 1 1
8 7
6 6 2 4 3 0 1 8
2 2
0 0

输出
复制

3
1
8
25
0

注意

在第一个测试用例中,我们对数组 $$$[0,2,1]$$$ 执行了三次操作。让我们计算第一次之后的结果:

  • 第一个元素变为 $$$\operatorname{MEX}(2,1)=0$$$
  • 第二个元素变为 $$$\operatorname{MEX}(0,1)=2$$$
  • 第三个元素变为 $$$\operatorname{MEX}(0,2)=1$$$

因此,在第一次操作之后,$$$[0,2,1]$$$ 再次变为$$$[0,2,1]$$$。可以看出,无论我们执行多少次操作,数组都不会改变,所以三次操作后最终的数组仍然是$$$[0,2,1]$$$。总和是$$$0+2+1=3$$$。

在第三个测试用例中,数组变为$$$[2,2,2,2]$$$。