Hop Sugoroku

题目描述

有一排 $N$ 个方格，编号为 $1,2,\dots,N$，以及一个长度为 $N$ 的序列 $A=(A_1,A_2,\dots,A_N)$。
最初，第 $1$ 个方格被涂成黑色，其他 $N-1$ 个方格被涂成白色，并且棋子放在第 $1$ 个方格上。 你可以重复以下操作任意次，也可以零次：

当棋子在方格 $i$ 上时，选择一个正整数 $x$ 并将棋子移动到方格 $i + A_i \times x$。 在这里，不能进行使 i + A_i \times x > N 的移动。

然后，将方格 $i + A_i \times x$ 涂成黑色。

求操作结束后可能被涂成黑色的方格集合的数目，对 $998244353$ 取模。

输入格式

输入从标准输入给出，格式如下： $N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出一个整数，表示答案。

5
1 2 3 1 1

8

1
200000

1

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

721419738

提示

所有输入值均为整数。 $1 \le N \le 2 \times 10^5$ $1 \le A_i \le 2 \times 10^5$共有八种可能被涂成黑色的方格集合：

方格 $1$ 方格 $1,2$ 方格 $1,2,4$ 方格 $1,2,4,5$ 方格 $1,3$ 方格 $1,4$ 方格 $1,4,5$ 方格 $1,5$
注意对 $998244353$ 取模。

标签: AtCoder|abc335F

来源

AtCoder|abc335F