32975번 - Corridor 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 6 | 4 | 4 | 66.667% |
문제
David wants to exit a secret science laboratory. He is in a corridor on the opposite end from the exit, so he will have to walk along the entire length of the corridor.
It would be straightforward to leave, but some teleporters are being tested in the corridor. The corridor consists of $N$ segments. Some segments contain a teleporter.
Each teleporter is configured to teleport stuff into a particular target segment. The target segment is always further from the exit (and thus closer to David's starting position) than the teleporter itself. Also each teleporter may be switched on or off.
When David enters (either walks or is teleported into) a segment with a turned-on teleporter, he is teleported into the target segment, and the teleporter turns off. When David enters a segment with a turned-off teleporter, he is not teleported, but the teleporter turns on.
All teleporters are turned on initially.
Find how long it will take David to leave the laboratory.
It takes one second for David to walk from one segment to the next. Teleportation is instantaneous. David will always walk towards the exit. Exiting the laboratory from the last segment of the corridor also takes one second.
Since the answer may be very large, output the remainder when David's total walking time (in seconds) is divided by $10^9 + 7$.
입력
The first line contains one integer $N$ ($1 \le N \le 100\,000$), the number of segments the corridor consists of.
The second line contains $N$ integers $A_1, A_2, \ldots, A_N$ ($1 \le A_i \le i$) denoting the teleporter targets. If $A_i = i$, then the $i$-th segment is empty. Otherwise the $i$-th segment contains a teleporter which teleports stuff into the $A_i$-th segment.
David starts at the $1$-st segment.
출력
Output one integer, David's time to exit the lab, modulo $10^9 + 7$.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $1 \le N \le 20$. |
| 2 | 12 | There are at most $20$ teleporters. |
| 3 | 19 | $A_i \in \{i-1, i\}$ for all $1 \le i \le N$. |
| 4 | 21 | $A_i \in \{1, i\}$ for all $1 \le i \le N$. |
| 5 | 21 | If $A_i \ne i$, then $A_j < a_i$ or $A_j > i$ for all $1 \le i < j \le N$. |
| 6 | 17 | No additional constraints. |
예제 입력 1
5 1 2 2 1 5
예제 출력 1
10
David will move in the following way ($\rightarrow$ denotes walking, $\Rightarrow$ teleportation): $1 \rightarrow 2 \rightarrow 3 \Rightarrow 2 \rightarrow 3 \rightarrow 4 \Rightarrow 1 \rightarrow 2 \rightarrow 3 \Rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow$ exit.
예제 입력 2
3 1 1 2
예제 출력 2
6
David will move in the following way: $1 \rightarrow 2 \Rightarrow 1 \rightarrow 2 \rightarrow 3 \Rightarrow 2 \Rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow$ exit.
예제 입력 3
5 1 1 1 1 1
예제 출력 3
31
채점 및 기타 정보
- 예제는 채점하지 않는다.