| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 94 | 73 | 70 | 85.366% |
We play a game with $n$ dots on a number line.
The initial coordinate of the $i$-th dot is $x_i$. These coordinates are distinct. Every dot starts moving simultaneously with the same constant speed.
Each dot moves in the direction of the closest dot (different from itself) until it meets another dot. In the case of a tie, it goes to the left. Two dots meet if they are in the same coordinate, after that, they stop moving.
After enough time, every dot stops moving. The result of a game is the number of distinct coordinates where the dots stop.
Because this game is too easy, calculate the sum of results when we play the game for every subset of the given $n$ dots that has at least two dots. As the result can be very large, print the sum modulo 10ドル^9+7$.
The first line contains one integer $n$ (2ドル \leq n \leq 3000$).
The next line contains $n$ integers $x_1, x_2, \ldots, x_n$ (1ドル \leq x_1 < x_2 < \ldots < x_n \leq 10^9$), where $x_i$ represents the initial coordinate of $i$-th dot.
Print the sum of results modulo 10ドル^9+7$.
4 1 2 4 6
11
In the first example, for a subset of size 2ドル,ドル two dots move toward each other, so there is 1ドル$ coordinate where the dots stop.
For a subset of size 3ドル,ドル the first dot and third dot move toward the second dot, so there is 1ドル$ coordinate where the dots stop no matter the direction where the second dot moves.
For $[1, 2, 4, 6],ドル the first and second dots move toward each other. For the third dot, initially, the second dot and the fourth dot are the closest dots. Since it is a tie, the third dot moves left. The fourth dot also moves left. So there is 1ドル$ coordinate where the dots stop, which is 1ドル.5$.
Because there are 6ドル$ subsets of size 2ドル,ドル 4ドル$ subsets of size 3ドル$ and one subset of size 4ドル,ドル the answer is 6ドル \cdot 1 + 4 \cdot 1 + 1 = 11$.
5 1 3 5 11 15
30
In the second example, for a subset of size 5ドル$ (when there are dots at 1ドル,ドル 3ドル,ドル 5ドル,ドル 11ドル,ドル 15ドル$), dots at 1ドル$ and 11ドル$ will move right and dots at 3ドル,ドル 5ドル,ドル 15ドル$ will move left.
Dots at 1ドル,ドル 3ドル,ドル 5ドル$ will eventually meet at 2ドル,ドル and dots at 11ドル$ and 15ドル$ will meet at 13ドル,ドル so there are 2ドル$ coordinates where the dots stop.
Contest > Codeforces > Codeforces Round 851 (Div. 2) D번