#P18786. [KOI2026 一轮] 跳跃
[KOI2026 一轮] 跳跃
[KOI2026 一轮] 跳跃(점프 / Jump)
题目描述
二维平面上有 个踏板,编号为 。踏板 位于点 。
给定正整数 。只有同时满足下列条件时,才能从踏板 跳到踏板 :
- ;
- 。
对于每个踏板 ,求从它出发,经过零次或多次跳跃后能够到达的不同踏板数量。起点自身也要计入答案。
输入格式
第一行两个整数 。
第二行 个整数 。
输出格式
输出一行 个整数。第 个数表示从踏板 出发能够到达的不同踏板数量。
样例 1
6 2
3 5 4 6 1 3
6 4 3 1 2 1
各起点的可达踏板集合分别为:、、、、、。
样例 2
6 3
1 4 8 9 10 15
2 1 3 2 1 1
样例 3
3 2
1 4 7
1 1 1
数据范围与子任务
所有输入均为整数。
- ;
- ;
- 。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 12 | |
| 2 | 32 | |
| 3 | 9 | |
| 4 | 23 | 所有 |
| 5 | 33 | |
| 6 | 41 | 无附加限制 |
原题满分为 150 分;本资料包保留原子任务及分值。时限 2 秒,内存限制 1024 MiB。