A16621 | $Mexification$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$，执行如下操作 $k$ 次： - 对于每个元素 $a_i$，令 $a_i$ 的值为 $\operatorname{mex}(a_1,a_2,...,a_{i-1},a_{i+1},a_{i+2},...,a_n)$。即：令 $a_i$ 的值为其他所有元素的 $\operatorname{mex}$。该计算是对所有元素同时进行的。 请计算数组在 $k$ 次操作之后所有元素之和。 对于整数集合 $d=\{d_1,d_2,...d_n\}$，$\operatorname{mex}(d)$ 定义为最小的且不包含在 $d$ 中的非负整数。

每个测试点包含多个测试用例。第一行包含测试用例数量 $t$，满足 $t \leq 10^4$。接下来，对于各个测试用例： - 第一行包含两个整数 $n$ 和 $k$，表示数组 $a$ 元素个数以及操作次数。保证 $2 \leq n \leq 2\times10^5$ 且 $1 \leq k \leq 10^9$； - 第二行包含 $n$ 个整数，依次表示 $a_1,a_2,...a_n$，保证对于任意 $a_i$ 有 $0 \leq a_i \leq n$。 保证所有测试用例的 $n$ 的和不会超过 $2 \times 10^5$。

每个测试用例一行，输出 $k$ 次操作之后所有元素的和。

输入 #1

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

输出 #1

C++ 编辑器

输入

输出