레이팅 미적용농부 존은 이익을 남기고 팔기 위해 세계적으로 유명한 우무(OohMoo) 우유를 만들려고 한다. 그는 채우려고 하는 병 \(N\) \((1 \leq N \leq 10^5)\)개를 가지고 있다. 각 병에는 처음에 우유가 \(m_i\) \((0 \leq m_i \leq 10^9)\)만큼 들어 있다. 매일 그는 \(A\) \((1 \le A \le N)\)개의 병을 골라 각 병에 우유 한 단위를 채운다.
불행히도, 우무 우유 사업에서 농부 존의 경쟁자인 농부 존팜(Nhoj)은 농부 존의 생산 과정을 알고 있으며 그의 사업을 방해할 계획을 가지고 있다. 매일 농부 존이 \(A\)개의 병을 채운 뒤, 농부 존팜은 서로 다른 비어 있지 않은 병 \(B\) \((0 \le B < A)\)개에서 각각 우유 한 단위를 몰래 훔친다. 들키지 않기 위해, 농부 존팜은 농부 존에게 발각될 가능성을 줄이도록 \(B\)를 \(A\)보다 엄격히 작게 선택한다.
\(D\) (\(1 \leq D \leq 10^9\))일이 지난 후, 농부 존은 우무 우유를 판매한다. 어떤 병에 우유가 \(M\) 단위 들어 있다면, 그 병은 \(M^2\) 무니에 팔린다.
농부 존팜이 어떻게 행동하든 농부 존이 최소 \(P\)의 이익을 보장받을 수 있고, 농부 존이 어떻게 행동하든 농부 존팜이 농부 존의 이익을 최대 \(P\)로 제한할 수 있는 유일한 이익을 \(P\)라고 하자. \(P\)를 \(10^9+7\)로 나눈 나머지를 출력하라.
Problem credits: Suhas Nagar
SCORING
- 입력 4-6: \(N,D\le 1000\).
- 입력 7-10: \(D\le 10^6\).
- 입력 11-20: 추가 제약 없음.
Problem credits: Suhas Nagar
입력의 첫째 줄에 \(N\)과 \(D\)가 주어지며, \(N\)은 병의 개수이고 \(D\)는 진행되는 일수이다.
입력의 둘째 줄에 \(A\)와 \(B\)가 주어지며, 각각 농부 존이 채우는 우유의 단위 수와 농부 존팜이 훔치는 우유의 단위 수를 나타낸다.
입력의 셋째 줄에 공백으로 구분된 \(N\)개의 정수 \(m_i\)가 주어지며, 각 병에 처음 들어 있는 우유의 양을 나타낸다.
\(P\)를 \(10^9+7\)로 나눈 나머지를 출력한다.
5 4
4 2
4 10 8 10 10546On 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\).
10 5
5 1
1 2 3 4 5 6 7 8 9 107775 1000000000
3 1
0 1 2 3 410Make sure you output \(P\) modulo \(10^9+7\).