P14840 [THUPC 2026 初赛] 宝石分组

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）初赛。 题解等资源可在 查看。

收藏家小蓝有 $n$ 个宝石，其中第 $i$ 个宝石的亮度为 $a_i$，现在小蓝想把这些宝石分为若干个组，满足每个宝石**恰好**被分在一个组中。 对于一组宝石，若该组内有 $k$ 个宝石，其亮度分别为 $b_1, b_2, \dots, b_k$，则小蓝认为这组宝石的美观值为 $\frac{(\sum_{i=1}^k b_i)^2}{k^2}$。对于一组宝石的分组方案，小蓝认为其美观度为所有组的**美观值之和**。 现在小蓝有 $q$ 个问题，每个问题形如若要求在分组时每组宝石中的宝石的个数在 $[l, r]$ 之间，则对于所有符合要求的分组方案，其美观度可以达到的**最大值**是多少。 由于答案可能是一个很大的分数 $\frac a b$，为了方便输出，您只需要回答它对 $10^9 + 7$ 取 模的结果，即您需要求出一个在 $[0, 10^9 + 7)$ 之间的整数 $c$ 使得 $a \equiv bc \pmod {10^9 + 7}$，可 以证明在本题的限制条件下，总存在符合条件的 $c$，且符合条件的 $c$ 唯一。 **特别的，如果不存在符合要求的分组方案，请输出 $-1$。**

第一行输入两个正整数 $n, q(~1 \leq n, q \leq 5 \times 10^5)$，表示宝石总个数与问题个数。 第二行输入 $n$ 个非负整数，其中第 $i$ 个非负整数表示第 $i$ 个宝石的亮度 $a_i~(0 \leq a_i \leq 10^8)$。 接下来 $q$ 行，每行两个正整数 $l, r~(1 \le l \le r \le n)$，表示若要求在分组时若每组宝石的个数在 $[l, r]$ 之间，对于所有符合要求的分组方案，其美观度可以达到的最大值。

输出共 $q$ 行，其中第 $i$ 行包含一个整数，表示第 $i$ 个问题的答案，即当要求每组宝石的个数在第 $i$ 个问题给出的区间之内时，所有符合要求的分组方案的美观度可以达到的最大值对 $10^9 + 7$ 取模的结果。特别的，如果不存在符合要求的分组方案，请输出 $−1$。

#### 样例 1 解释 对于第一个问题，最优的分组方案为每个宝石各分配到一个单独的组中，即 $\{13\}, \{9\}, \{7\}, \{5\}, \{6\}, \{10\}$，此时美观值为 $460$，取到最大值。 对于第二个问题，仅存在唯一的分组方案 $\{13, 9, 7, 5, 6, 10\}$，此时美观值取到最大 值 $\frac{625}{9}$，对 $10^9 + 7$ 取模的结果为 $444444517$。 对于第三个问题，最优的分组方案为 $\{13, 10\}, \{9, 7\}, \{5, 6\}$，此时美观值取到最大值 $\frac{453}{2}$ ，对 $10^9 + 7$ 取模的结果为 $500000230$。 对于第四个问题，要求每个组的大小必须为 $4$，而宝石总数 $6$ 不是 $4$ 的倍数，故在分组时总会存在一些剩余的宝石无法分组，因此不存在符合条件的分组方案，所以输出 $−1$。