← 返回题目列表

Codeforces · 1787/D

D. 轴上游戏

中文机器翻译题面 查看原题

有 $$$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$$$(设置$$$a_x := y$$$)。找到不同对 $$$(x,y)$$$ 的数量,以便您在进行更改后开始的游戏以有限数量的步骤结束。

请注意,您不必满足 $$$a_x\not=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$$$ 。

在第二个测试用例中,对是 $$$(1,-2),(1,-1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)$$$。

在第四个测试用例中,这些对是 $$$(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,1),(2,2)$$$。