Problem 3D. Summation(equal version)

Problem 3D. Summation(equal version)

Problem 3D. Summation(equal version)

时间限制:1000ms

空间限制:256MB

题目描述

给定一个长度为 \(n\) ,下标从 \(1\) 开始的的序列 \(a\) ,请计算下列式子的值:
\[ \sum_{i = 1} ^ {n} \sum_{j = 1} ^{i} (a_i == a_j) \]
也就是说,你需要计算有多少对二元组 \((i, j)\) (\(1 \le i \le j \le n\)) 满足 \(a_i = a_j\)

输入格式

第一行一个正整数 \(T\),代表测试数据组数。

对于每一组有两行输入:

第一行一个整数 \(n\) ,代表序列 \(a\) 的长度。

第二行包含 \(n\) 个整数,用空格隔开,代表序列 \(a\) 的 \(n\) 个数。

输出格式

输出 \(T\) 行,每行一个整数,代表该序列要计算式子的结果。

样例输入

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

样例输出

10
3
9

样例解释

对于第三组数据,满足条件的二元组为 \((1, 1)\), \((1, 3)\), \((1, 5)\), \((2, 2)\), \((2, 4)\), \((3, 3)\), \((3, 5)\), \((4, 4)\), \((5, 5)\)

数据规模与约定

对于 \(60\%\) 的数据,\(1 \le T \le 10^3\), \(1 \le n \le 10^3\), \(n\) 的总和不超过 \(10^3\),

对于 \(100\%\) 的数据,\(1 \le T \le 10^5\), \(1 \le n \le 10^5\), \(n\) 的总和不超过 \(10^5\), 序列中的每个数满足 \(-10^9 \le a_i \le 10^9\)

信息

ID
1578
难度
9
分类
(无)
标签
(无)
递交数
2
已通过
1
通过率
50%
上传者

相关

在下列比赛中:

2024春 悬赏令第三周