#PU1523. USACO 2025 US Open Contest, Gold — Problem 3. OohMoo Milk

    ID: 1677 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:open25来源:usaco.orgscoring:equal_test_cases模拟

USACO 2025 US Open Contest, Gold — Problem 3. OohMoo Milk

USACO 2025 US Open Contest, Gold — Problem 3. OohMoo Milk

题目描述

Farmer John is trying to make his world's famous OohMoo Milk to sell for a profit. He has NN (1≤N≤105)(1 \leq N \leq 10^5) bottles that he is trying to fill. Each bottle initially contains some amount of milk mim_i (0≤mi≤109)(0 \leq m_i \leq 10^9). Every day, he takes AA (1≤A≤N)(1 \le A \le N) bottles and fills each bottle with one unit of milk. Unfortunately, Farmer Nhoj, Farmer John's competitor in the business of OohMoo Milk, knows about Farmer John's production processes and has a plan to curtail his business. Every day, after Farmer John fills his AA bottles, Farmer Nhoj will sneakily steal one unit of milk from each of BB (0≤B<A)(0 \le B < A) different nonempty bottles. To remain sneaky, Farmer Nhoj chooses BB so that it is strictly less than AA, so that it is less likely for Farmer John to discover him. After DD (1≤D≤1091 \leq D \leq 10^9) days, Farmer John will sell his OohMoo Milk. If a bottle has MM units of milk, it will sell for M2M^2 moonies. Let PP be the unique profit such that FJ can guarantee that he makes at least PP profit regardless of how FN behaves, and FN can guarantee that FJ makes at most PP profit regardless of how FJ behaves. Output the value of PP modulo 109+710^9+7.

输入格式

The first line of the input contains NN and DD, where NN is the number of bottles and DD is the number of days that take place. The second line of the input contains AA and BB representing the number of units of milk that Farmer John fills and Farmer Nhoj steals respectively. The third line of the input contains NN space-separated integers mim_i representing the initial amount of milk in each bottle.

输出格式

(见题面原文)

数据范围

Inputs 4-6: N,D≤1000N,D\le 1000. Inputs 7-10: D≤106D\le 10^6. Inputs 11-20: No additional constraints. Problem credits: Suhas Nagar

样例

样例 1

5 4
4 2
4 10 8 10 10
546
On the first day, Farmer John could add milk to the second, third,
fourth, and fifth bottles. Then, Farmer Nhoj could remove milk from the
second and fourth bottles.
Thus, the new amount of milk in each bottle is
$$[4, 10, 8, 10, 10] \to [4, 11, 9, 11, 11] \to [4, 10, 9, 10, 11].$$
After four days, the amount of milk in each bottle could be
$$[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].$$
The total amount of moonies Farmer John would make in this situation is $4^2+11^2+11^2+12^2+12^2 = 546$. It can be shown that this is the value
of $P$.

样例 2

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

样例 3

5 1000000000
3 1
0 1 2 3 4
10
Make sure you output $P$ modulo $10^9+7$.