CF1990C Mad MAD Sum

题目描述

我们定义数组中的 $\operatorname{MAD}$（最大重复出现数）为数组中出现至少两次的最大数字。具体来说，如果没有任何数字出现至少两次，则 $\operatorname{MAD}$ 的值为 $0$。

例如，$\operatorname{MAD}([1, 2, 1]) = 1$，$\operatorname{MAD}([2, 2, 3, 3]) = 3$，$\operatorname{MAD}([1, 2, 3, 4]) = 0$。

给定一个长度为 $n$ 的数组 $a$。初始时，有一个变量 $sum$，其值为 $0$。

执行如下过程，直到 $a$ 中所有数字都变为 $0$ 为止，循环进行：

1. 令 $sum := sum + \sum_{i=1}^{n} a_i$；
2. 令 $b$ 为长度为 $n$ 的数组。对于所有 $1 \le i \le n$，令 $ b_i :=\ \operatorname{MAD}([a_1, a_2, \ldots, a_i]) $，然后对于所有 $1 \le i \le n$，令 $a_i := b_i$。

请你求出该过程结束后 $sum$ 的值。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 2 \cdot 10^4$），表示测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示数组 $a$ 的长度；
• 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），表示数组的元素。

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

输出格式

对于每个测试用例，输出一个整数，表示该过程结束后 $sum$ 的值，每个测试用例输出一行。

输入输出样例 #1

输入 #1

4
1
1
3
2 2 3
4
2 1 1 2
4
4 4 4 4

输出 #1

1
13
9
40

说明/提示

在第一个测试用例中，初始时 $a=[1]$。

第一次循环：

1. 令 $sum := sum + a_1 = 0+1=1$；
2. 令 $ b_1 :=\ \operatorname{MAD}([a_1])=\ \operatorname{MAD}([1])=0 $，然后令 $a_1 := b_1$。

第一次循环后，$a=[0]$，过程结束。最终 $sum=1$。

在第二个测试用例中，初始时 $a=[2,2,3]$。

第一次循环后，$a=[0,2,2]$，$sum=7$。

第二次循环后，$a=[0,0,2]$，$sum=11$。

第三次循环后，$a=[0,0,0]$，$sum=13$，过程结束。

最终 $sum=13$。

由 ChatGPT 4.1 翻译