A15725 | Moving Dots
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
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 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.
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$ .
输入输出样例
输入 #1
4 1 2 4 6
输出 #1
11
输入 #2
5 1 3 5 11 15
输出 #2
30
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$ .
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.
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$ .
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.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted