A7104 | Sakurako's Box
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
Sakurako 有一个装满 $n$ 个球的盒子。每个球都有自己的数值。她想和朋友打个赌，朋友如果从盒子中随机选出两个球（可以是不同的两球，即使它们有相同的数值），这两个球数值的乘积能够等于 Sakurako 事先猜测到的一个数。
因为 Sakurako 是概率学方面的专家，她知道最明智的猜测应该是期望值，但她忘了如何去计算。请帮助她计算出这个数组中任意两个元素乘积的期望值。
可以证明，该期望值的形式为 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 是非负整数，且 $Q \ne 0$。你需要计算并输出 $P \cdot Q^{-1} \bmod (10^9+7)$ 的结果。
因为 Sakurako 是概率学方面的专家，她知道最明智的猜测应该是期望值，但她忘了如何去计算。请帮助她计算出这个数组中任意两个元素乘积的期望值。
可以证明，该期望值的形式为 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 是非负整数，且 $Q \ne 0$。你需要计算并输出 $P \cdot Q^{-1} \bmod (10^9+7)$ 的结果。
输入格式
输入的第一行是一个整数 $t$，表示测试用例的数量。
接下来的每一个测试用例的第一行是一个整数 $n$，表示数组中元素的数量。
接下来的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组中的元素值。
保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。
接下来的每一个测试用例的第一行是一个整数 $n$，表示数组中元素的数量。
接下来的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组中的元素值。
保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。
输出格式
对每个测试用例，输出 $P \cdot Q^{-1} \bmod (10^9+7)$ 的结果。
输入输出样例
输入 #1
3 3 3 2 3 4 2 2 2 4 5 1 2 3 4 5
输出 #1
7 6 500000012
样例解释
- 在第一个测试用例中，Sakurako 的朋友可以选择这些球对：$(a_1, a_2)$、$(a_1, a_3)$ 和 $(a_2, a_3)$。它们的乘积分别是 $3 \times 2 = 6$、$3 \times 3 = 9$ 和 $3 \times 2 = 6$，所以期望值计算结果为 $\frac{6 + 9 + 6}{3} = 7$。
- 在第二个测试用例中，朋友可以选择的球对有：$(a_1, a_2)$、$(a_1, a_3)$、$(a_1, a_4)$、$(a_2, a_3)$、$(a_2, a_4)$ 和 $(a_3, a_4)$。它们的乘积分别为 $2 \times 2 = 4$、$2 \times 2 = 4$、$2 \times 4 = 8$、$2 \times 2 = 4$、$2 \times 4 = 8$ 和 $2 \times 4 = 8$，所以期望值为 $\frac{4 + 4 + 8 + 4 + 8 + 8}{6} = \frac{36}{6} = 6$。
数据范围
$1 \le t \le 10^4$
$2 \le n \le 2 \cdot 10^5$
$0 \le a_i \le 10^9$
保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？