310134: CF1787D. Game on Axis

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Game on Axis

题意翻译

### 题目描述 有 $n$ 个点,第 $i$ 个点上有数字 $a_i$,你在这些点上面玩一个游戏,初始在点 $1$。当你在点 $i$ 时: - 若 $1\le i\le n$,则你会跳到点 $i+a_i$; - 否则游戏结束。 在游戏开始前,你可以选择一对 $x$ 和 $y$($1\le x\le n,-n\le y\le n$),并将 $a_x$ 赋值为 $y$。请求出这样的 $(x,y)$ 的对数使得可以在有限步内结束游戏。注意即使 $a_x$ 已经等于 $y$ 了,$(x,y)$ 也可能是合法的。 ### 输入格式 输入第一行一个正整数 $t$($1\le t\le 10^4$)表示数据组数。 每组测试数据第一行一个正整数 $n$($1\le n\le 2\cdot 10^5$)表示点的个数。 第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$($-n \le a_i \le n$)表示序列 $a$。 保证所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$。 ### 样例解释 第一组数据中,符合条件的 $(x,y)$ 为 $(1,-1)$ 和 $(1,1)$,分别对应路径 $1\rightarrow 0$ 和 $1\rightarrow 2$。注意 $(1,2)$ 不合法因为 $n=1$,$y=2$ 不符合 $-n\le y\le n$;$(1,0)$ 也不合法因为你将永远从 $1$ 走到 $1$ 而无法结束游戏。 第二组数据中,符合条件的 $(x,y)$ 为 $(1,-2),(1,-1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)$。 第三组数据中,符合条件的 $(x,y)$ 为 $(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,1),(2,2)$。

题目描述

There are $ n $ points $ 1,2,\ldots,n $ , each point $ i $ has a number $ a_i $ on it. You're playing a game on them. Initially, you are at point $ 1 $ . When you are at point $ i $ , take following steps: - If $ 1\le i\le n $ , go to $ i+a_i $ , - Otherwise, the game ends. Before the game begins, you can choose two integers $ x $ and $ y $ satisfying $ 1\le x\le n $ , $ -n \le y \le n $ and replace $ a_x $ with $ y $ (set $ a_x := y $ ). Find the number of distinct pairs $ (x,y) $ such that the game that you start after making the change ends in a finite number of steps. Notice that you do not have to satisfy $ a_x\not=y $ .

输入输出格式

输入格式


Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1\le t\le 10^4) $ — the number of test cases. The first line of each test case contains one integer $ n $ ( $ 1\le n\le 2\cdot 10^5 $ ) — the number of points. The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ -n \le a_i \le n $ ) — the numbers on the axis. It's guaranteed that the sum of $ n $ does not exceed $ 2\cdot 10^5 $ .

输出格式


For each test case, print a line containing a single integer — the number of distinct pairs $ (x,y) $ with which the game ends.

输入输出样例

输入样例 #1

9
1
0
2
-1 0
2
1 -1
2
1 1
3
-1 -2 -1
3
1 -2 -1
4
-1 4 -2 1
5
1 1 1 1 -4
5
1 1 1 1 1

输出样例 #1

2
8
6
7
20
17
34
30
40

说明

In the first test case, the pairs $ (x,y) $ with which the game ends are $ (1,-1) $ and $ (1,1) $ , corresponding to the routes $ 1\rightarrow 0 $ and $ 1\rightarrow 2 $ . Note that $ (1,2) $ is invalid since when $ n=1 $ , $ y=2 $ violates $ -n\le y\le n $ . $ (1,0) $ is also invalid since you will go from $ 1 $ to $ 1 $ forever. In the second test case, the pairs are $ (1,-2),(1,-1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2) $ . In the fourth test case, the pairs are $ (1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,1),(2,2) $ .

Input

题意翻译

### 题目描述 有 $n$ 个点,第 $i$ 个点上有数字 $a_i$,你在这些点上面玩一个游戏,初始在点 $1$。当你在点 $i$ 时: - 若 $1\le i\le n$,则你会跳到点 $i+a_i$; - 否则游戏结束。 在游戏开始前,你可以选择一对 $x$ 和 $y$($1\le x\le n,-n\le y\le n$),并将 $a_x$ 赋值为 $y$。请求出这样的 $(x,y)$ 的对数使得可以在有限步内结束游戏。注意即使 $a_x$ 已经等于 $y$ 了,$(x,y)$ 也可能是合法的。 ### 输入格式 输入第一行一个正整数 $t$($1\le t\le 10^4$)表示数据组数。 每组测试数据第一行一个正整数 $n$($1\le n\le 2\cdot 10^5$)表示点的个数。 第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$($-n \le a_i \le n$)表示序列 $a$。 保证所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$。 ### 样例解释 第一组数据中,符合条件的 $(x,y)$ 为 $(1,-1)$ 和 $(1,1)$,分别对应路径 $1\rightarrow 0$ 和 $1\rightarrow 2$。注意 $(1,2)$ 不合法因为 $n=1$,$y=2$ 不符合 $-n\le y\le n$;$(1,0)$ 也不合法因为你将永远从 $1$ 走到 $1$ 而无法结束游戏。 第二组数据中,符合条件的 $(x,y)$ 为 $(1,-2),(1,-1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)$。 第三组数据中,符合条件的 $(x,y)$ 为 $(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,1),(2,2)$。

Output

**题目大意:**

存在 $ n $ 个点,编号为 $ 1,2,\ldots,n $,每个点 $ i $ 上有一个数字 $ a_i $。你从点 $ 1 $ 开始玩游戏,当你处于点 $ i $ 时,执行以下步骤:

- 如果 $ 1\le i\le n $,则移动到点 $ i+a_i $;
- 否则,游戏结束。

在游戏开始前,你可以选择两个整数 $ x $ 和 $ y $(满足 $ 1\le x\le n $,$ -n \le y \le n $),并将 $ a_x $ 的值替换为 $ y $。求出这样的 $ (x,y) $ 对的数量,使得游戏在有限步内结束。注意即使 $ a_x $ 已经等于 $ y $,$ (x,y) $ 也可能是合法的。

**输入格式:**

输入包含多个测试用例。第一行包含一个整数 $ t $($ 1\le t\le 10^4 $)——测试用例的数量。

每个测试用例的第一行包含一个整数 $ n $($ 1\le n\le 2\cdot 10^5 $)——点的数量。

第二行包含 $ n $ 个整数 $ a_1,a_2,\ldots,a_n $($ -n \le a_i \le n $)——数轴上的数字。

保证所有测试用例的 $ n $ 之和不超过 $ 2\cdot 10^5 $。

**输出格式:**

对于每个测试用例,打印一行,包含一个整数——使得游戏结束的不同 $ (x,y) $ 对的数量。

**输入输出样例:**

**输入样例 #1:**
```
9
1
0
2
-1 0
2
1 -1
2
1 1
3
-1 -2 -1
3
1 -2 -1
4
-1 4 -2 1
5
1 1 1 1 -4
5
1 1 1 1 1
```

**输出样例 #1:**
```
2
8
6
7
20
17
34
30
40
```

**说明:**

在第一组数据中,符合条件的 $ (x,y) $ 为 $ (1,-1) $ 和 $ (1,1) $,分别对应路径 $ 1\rightarrow 0 $ 和 $ 1\rightarrow 2 $。注意 $ (1,2) $ 不合法因为当 $ n=1 $,$ y=2 $ 不符合 $ -n\le y\le n $;$ (1,0) $ 也不合法因为你将永远从 $ 1 $ 走到 $ 1 $ 而无法结束游戏。

在第二组数据中,符合条件的 $ (x,y) $ 为 $ (1,-2),(1,-1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2) $。

在第四组数据中,符合条件的 $ (x,y) $ 为 $ (1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,1),(2,2) $。**题目大意:** 存在 $ n $ 个点,编号为 $ 1,2,\ldots,n $,每个点 $ i $ 上有一个数字 $ a_i $。你从点 $ 1 $ 开始玩游戏,当你处于点 $ i $ 时,执行以下步骤: - 如果 $ 1\le i\le n $,则移动到点 $ i+a_i $; - 否则,游戏结束。 在游戏开始前,你可以选择两个整数 $ x $ 和 $ y $(满足 $ 1\le x\le n $,$ -n \le y \le n $),并将 $ a_x $ 的值替换为 $ y $。求出这样的 $ (x,y) $ 对的数量,使得游戏在有限步内结束。注意即使 $ a_x $ 已经等于 $ y $,$ (x,y) $ 也可能是合法的。 **输入格式:** 输入包含多个测试用例。第一行包含一个整数 $ t $($ 1\le t\le 10^4 $)——测试用例的数量。 每个测试用例的第一行包含一个整数 $ n $($ 1\le n\le 2\cdot 10^5 $)——点的数量。 第二行包含 $ n $ 个整数 $ a_1,a_2,\ldots,a_n $($ -n \le a_i \le n $)——数轴上的数字。 保证所有测试用例的 $ n $ 之和不超过 $ 2\cdot 10^5 $。 **输出格式:** 对于每个测试用例,打印一行,包含一个整数——使得游戏结束的不同 $ (x,y) $ 对的数量。 **输入输出样例:** **输入样例 #1:** ``` 9 1 0 2 -1 0 2 1 -1 2 1 1 3 -1 -2 -1 3 1 -2 -1 4 -1 4 -2 1 5 1 1 1 1 -4 5 1 1 1 1 1 ``` **输出样例 #1:** ``` 2 8 6 7 20 17 34 30 40 ``` **说明:** 在第一组数据中,符合条件的 $ (x,y) $ 为 $ (1,-1) $ 和 $ (1,1) $,分别对应路径 $ 1\rightarrow 0 $ 和 $ 1\rightarrow 2 $。注意 $ (1,2) $ 不合法因为当 $ n=1 $,$ y=2 $ 不符合 $ -n\le y\le n $;$ (1,0) $ 也不合法因为你将永远从 $ 1 $ 走到 $ 1 $ 而无法结束游戏。 在第二组数据中,符合条件的 $ (x,y) $ 为 $ (1,-2),(1,-1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2) $。 在第四组数据中,符合条件的 $ (x,y) $ 为 $ (1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,1),(2,2) $。

加入题单

上一题 下一题 算法标签: