CF1513E Cost Equilibrium

如果一个数组的所有元素都相等，则称该数组为美丽数组。 你可以对一个数组进行如下操作任意次： 1. 选择两个下标 $i$ 和 $j$（$1 \leq i, j \leq n$），以及一个整数 $x$（$1 \leq x \leq a_i$）。令 $i$ 为源下标，$j$ 为汇下标。 2. 将第 $i$ 个元素减少 $x$，将第 $j$ 个元素增加 $x$。操作后，第 $i$ 个和第 $j$ 个元素分别变为 $a_i - x$ 和 $a_j + x$。 3. 此操作的代价为 $x \cdot |j - i|$。 4. 此后，第 $i$ 个下标不能再作为汇点，第 $j$ 个下标不能再作为源点。 一次变换的总代价为所有操作代价之和。例如，数组 $[0, 2, 3, 3]$ 可以通过代价 $1 \cdot |1-3| + 1 \cdot |1-4| = 5$ 变换为美丽数组 $[2, 2, 2, 2]$。 如果一个数组可以被变换为美丽数组，并且这种变换的总代价是唯一确定的（即变换为美丽数组的最小代价等于最大代价），则称该数组为平衡数组。 给定一个长度为 $n$ 的非负整数数组 $a_1, a_2, \ldots, a_n$，你的任务是求出有多少个平衡数组是该数组的排列。若两个数组在某些位置的元素不同，则认为它们不同。由于答案可能很大，请输出对 $10^9 + 7$ 取模的结果。

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）——数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$）。

输出一个整数，表示平衡排列的数量，对 $10^9+7$ 取模。

在第一个样例中，$[1, 2, 3]$ 是一个有效的排列，因为我们可以将值为 $3$ 的下标作为源点，值为 $1$ 的下标作为汇点。这样变换后可以得到美丽数组 $[2, 2, 2]$，总代价为 $2$。可以证明这是唯一能将该数组变为美丽数组的变换。同理，可以检查其他排列。 在第二个样例中，$[0, 0, 4, 4]$ 和 $[4, 4, 0, 0]$ 都是平衡排列。 在第三个样例中，所有排列都是平衡的。 由 ChatGPT 4.1 翻译