← 返回题目列表

Codeforces · 2185/G

G. 混合 MEX

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

你得到了 $$$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_1, a_2, \ldots a_n$$$ 中选择任何其他数组 不是 $$$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 \le n \le 2 \cdot 10^5$$$) — 数组的数量。

接下来的 $$$n$$$ 行以 $$$l_i$$$ ($$$1 \le l_i \le 10^5$$$) 开头 - 第 $$$i$$$ 数组的长度 - 然后包含 $$$l_i$$$ 整数 $$$a_1, a_2, \ldots, a_{l_i}$$$ ($$$0 \le a_{i_j} \le 10^6$$$) — 数组 $$$a_i$$$。

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

输出

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

示例

输入
复制

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

输出
复制

6
0
50
8
43
19202

注意

对于第一个测试用例,我们有 3 种可能的不同操作:

  • $$$i = 1, j = 1, k = 2$$$:数组现在为 [] 和 [$$$0, 1, 2$$$],其 $$$\operatorname{mex}$$$ 分别为 $$$0$$$ 和 $$$3$$$,因此操作的值为 $$$3$$$。
  • $$$i = 2, j = 1, k = 1$$$:数组现在为 [$$$0, 1$$$] 和 [$$$2$$$],其 $$$\operatorname{mex}$$$ 分别为 $$$2$$$ 和 $$$0$$$,因此操作的值为 $$$2$$$。
  • $$$i = 2, j = 2, k = 1$$$:数组现在为 [$$$0, 2$$$] 和 [$$$1$$$],其 $$$\operatorname{mex}$$$ 分别为 $$$1$$$ 和 $$$0$$$,因此操作的值为 $$$1$$$。

对于第二个测试用例,由于没有数组包含零,因此所有操作的值将为 $$$0$$$。