← 返回题目

题库练习 Mixing MEXes

← 上一题下一题 →

A16482 | $Mixing MEXes$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定 $n$ 个数组 $a_1, a_2, \ldots, a_n$。 对这些数组恰好执行一次如下操作： - 在 $a_1, a_2, \ldots, a_n$ 中任选一个数组。假设选择了 $a_i$（$1 \leq i \leq n$）。 - 在该数组 $a_i$ 内任选一个元素。假设选择了 $a_i$ 的第 $j$ 个元素，记为 $a_{i,j}$（$1 \leq j \leq |a_i|$，其中 $|a_i|$ 表示数组 $a_i$ 的长度）。 - 在其它数组中选一个（不能是 $a_i$ 本身）。假设选择了 $a_k$（$1 \leq k \leq n, k \neq i$）。 - 将 $a_{i,j}$ 加到数组 $a_k$ 的末尾，并且从 $a_i$ 中移除 $a_{i,j}$。 - 本次操作 $(i, j, k)$ 的价值定义为操作执行后所有数组的 $\operatorname{MEX}$ 之和。更正式一点，操作后的价值为 $\sum_{i=1}^{n} \operatorname{MEX}(a_i)$。 请计算所有可能的不同独立操作的价值之和。 两个操作不同，当且仅当有序三元组 $(i, j, k)$ 不同。 $\operatorname{MEX}(a)$ 定义为不在数组中的最小非负整数。例如，$\operatorname{MEX}([1, 2, 0, 5]) = 3$，而 $\operatorname{MEX}([1, 2, 4, 9]) = 0$。

输入格式

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例数量。 每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2 \times 10^5$），表示数组的个数。 接下来 $n$ 行，每行以 $l_i$（$1 \leq l_i \leq 10^5$）开头，表示第 $i$ 个数组的长度，后跟 $l_i$ 个整数 $a_1, a_2, \ldots, a_{l_i}$（$0 \leq a_{i_j} \leq 10^6$），构成数组 $a_i$。 保证所有测试用例中 $l_i$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出所有可能不同操作的价值之和。

输入输出样例

输入 #1

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

输出 #1

C++ 编辑器

输入

输出