AdditionalFile7006.zip

#7006. 「THUPC 2026 初赛」宝石分组

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

收藏家小蓝有 $n$ 个宝石，其中第 $i$ 个宝石的亮度为 $a_{i}$，现在小蓝想把这些宝石分为若干个组，满足每个宝石恰好被分在一个组中。

对于一组宝石，若该组内有 $k$ 个宝石，其亮度分别为 $b_{1}, b_{2}, \ldots, b_{k}$，则小蓝认为这组宝石的美观值为 $\frac{\left(\sum_{i=1}^{k} b_{i}\right)^{2}}{k^{2}}$。对于一组宝石的分组方案，小蓝认为其美观度为所有组的美观值之和。

现在小蓝有 $q$ 个问题，每个问题形如若要求在分组时每组宝石中的宝石的个数在 $[l, r]$ 之间，则对于所有符合要求的分组方案，其美观度可以达到的最大值是多少。

由于答案可能是一个很大的分数 $\frac{a}{b}$ ，为了方便输出，您只需要回答它对 $10^{9}+7$ 取模的结果，即您需要求出一个在 $\left[0,10^{9}+7\right)$ 之间的整数 $c$ 使得 $a \equiv b c \pmod{10^{9}+7}$，可以证明在本题的限制条件下，总存在符合条件的 $c$ ，且符合条件的 $c$ 唯一。特别的，如果不存在符合要求的分组方案，请输出 $-1$。

输入格式

从标准输入读入数据。

第一行输入两个正整数 $n, q$ $\left(1 \leq n, q \leq 5 \times 10^{5}\right)$，表示宝石总个数与问题个数。

第二行输入 $n$ 个非负整数，其中第 $i$ 个非负整数表示第 $i$ 个宝石的亮度 $a_{i}$ $\left(0 \leq a_{i} \leq 10^{8}\right)$。

接下来 $q$ 行，每行两个正整数 $l, r$ $\left(1 \leq l \leq r \leq n\right)$，表示若要求在分组时若每组宝石的个数在 $[l, r]$ 之间，对于所有符合要求的分组方案，其美观度可以达到的最大值。

输出格式

输出到标准输出。

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

样例 1

输入

6 4
13 9 7 5 6 10
1 5
4 6
2 3
4 4

输出

460
444444517
500000230
-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$。

题目使用协议

来自 THUPC2026（2026年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2026 初赛 官方仓库（https://gitlink.org.cn/thusaa/thupc2026pre）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。