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) $ .

**题目大意：**

存在 $ 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) $。