← 返回比赛

已结束 GESP排位赛 #4

← 上一题下一题 →

A1753 | $树枝$

来源官方 / 2024

时间限制2s

内存限制128MB

通过 / 提交0/0

题目描述

出题人：小张张五 本题时限2秒。 小星在学校里一共捡了 $n$ 根树枝，第 $i$ 树枝长度为 $a_i$，现在小星想挑三根树枝，并让他们头尾相接、围成一个三角形，那么他有几种围三角形的方案。 两种方案是不同的当且仅当一个方案里存在至少一根树枝，这根树枝在另一个方案不存在。

输入格式

本题的测试点包含多个测试数据。 第一行一个正整数 $T$，代表数据组数。 接下来 $T$ 组，每组中： 第一行包含一个正整数 $n$，代表树枝数量。 第二行包含 $n$ 个正整数，$a_1,a_2,...,a_n$，代表每根树枝的长度。

输出格式

$T$ 行，每行一个整数，代表方案数。

输入输出样例

输入 #1

输出 #1

3
7

数据范围 对于 $100\%$ 的测试点，保证 $1\leq T \leq 10$，$1\leq n\leq5000$，$1\leq a_i\leq1\times10^9$。 测试点编号$n\leq$$a_i\leq$$1$$3$$1\times10^9$$2\sim3$$300$$1\times10^9$$4\sim5$$5000$$3$$6\sim7$$5000$$1\times10^5$$8\sim10$$5000$$1\times10^9$ 样例解释 在第一组测试数据中，不同的方案有 $\{1,2,2\},\{1,2,2\},\{2,2,3\}$，前两种方案中长度为 $1$ 的树枝用的是两根不同的，所以看作是不同的方案。 在第二组测试数据中，不同的方案有 $\{2,3,4\},\{2,4,5\},\{2,5,6\},\{3,4,5\},\{3,4,6\},\{3,5,6\},\{4,5,6\}$ 。

C++ 编辑器

输入

输出