← 返回题目列表

AtCoder · arc223_c

C. 成对距离的整积

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

分数: 500 点

问题陈述

给你一个序列 A of N 正整数。
求余数 \prod_{1 \leq i < j \leq N}|A_i-A_j| 除以 N.

解决 输入文件中的 T 每个输入的测试用例。

约束

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 总和 N 所有测试用例最多 2 \times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例 \mathrm{case}_t 按以下格式给出:

N  
A_1 A_2 \ldots A_N

输出

输出总共的答案 T 行。 的 t- 第行应包含以下问题的答案 t- 第一个测试用例。


示例输入 1

3
3
1 9 5
3
2 2 3
5
11 33 22 55 44

示例输出 1

2
0
3

对于第一个测试用例, |A_1-A_2| \times |A_1-A_3| \times |A_2-A_3|=8 \times 4 \times 4=128,以及除以的余数 3 is 2.