OohMoo Milk

题目描述

Farmer John 正尝试制作他举世闻名的 OohMoo 牛奶以获取利润。他有 $N$ 个 $(1 \leq N \leq 10^5)$ 瓶子需要装满。每个瓶子最初含有一定量的牛奶 $m_i$ $(0 \leq m_i \leq 10^9)$。每天，他会选取 $A$ 个 $(1 \le A \le N)$ 瓶子，并给每个瓶子加 1 单位牛奶。 不幸的是，Farmer Nhoj（Farmer John 在 OohMoo 牛奶生意上的竞争对手）了解 Farmer John 的生产流程，并打算遏制他的生意。每天，在 Farmer John 给他的 $A$ 个瓶子加完牛奶后，Farmer Nhoj 会偷偷从另外 $B$ 个 $(0 \le B < A)$ 不同的、且当前非空的瓶子中各偷走 1 单位牛奶。为了保持隐蔽，Farmer Nhoj 会选择严格小于 $A$ 的 $B$，这样 Farmer John 不太容易发现他。 经过 $D$ 天 ($1 \leq D \leq 10^9$) 后，Farmer John 将出售他的 OohMoo 牛奶。若某个瓶子中有 $M$ 单位牛奶，则它将以 $M^2$ 个 moonies 的价格售出。 设 $P$ 为唯一的利润值，使得无论 Farmer Nhoj 如何行动，Farmer John 都能保证获得至少 $P$ 的利润；同时无论 Farmer John 如何行动，Farmer Nhoj 都能保证 Farmer John 的利润至多为 $P$。输出 $P$ 对 $10^9+7$ 取模的结果。

输入格式

第一行输入 $N$ 和 $D$，其中 $N$ 为瓶子数量，$D$ 为经过的天数。 第二行输入 $A$ 和 $B$，分别表示 Farmer John 每天添加的牛奶单位数以及 Farmer Nhoj 每天偷走的牛奶单位数。 第三行包含 $N$ 个以空格分隔的整数 $m_i$，表示每个瓶子初始的牛奶量。

输出格式

输出 $P$ 对 $10^9+7$ 取模的结果。

5 4
4 2
4 10 8 10 10

546

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

777

5 1000000000
3 1
0 1 2 3 4

10

提示

第一天，Farmer John 可以给第 2、3、4、5 个瓶子加牛奶。然后，Farmer Nhoj 可以从第 2 和第 4 个瓶子中偷走牛奶。 因此，每个瓶子中的新牛奶量为

$$[4, 10, 8, 10, 10] \to [4, 11, 9, 11, 11] \to [4, 10, 9, 10, 11].$$

四天后，每个瓶子中的牛奶量可能为

$$[4, 10, 8, 10, 10] \to [4, 10, 9, 10, 11] \to [4, 10, 10, 11, 11] \to [4, 11, 11, 11, 11] \to [4, 11, 11, 12, 12].$$

在这种情况下，Farmer John 能获得的 moonies 总数为 $4^2+11^2+11^2+12^2+12^2 = 546$。可以证明这就是 $P$ 的值。 请确保输出 $P$ 对 $10^9+7$ 取模的结果。 评分： Inputs 4-6：$N,D\le 1000$。 Inputs 7-10：$D\le 10^6$。 Inputs 11-20：无额外限制。 题目鸣谢：Suhas Nagar

标签: USACO|2025|Gold

来源

USACO|2025|Gold