AT_abc335_f [ABC335F] Hop Sugoroku

题目描述

有 $N$ 个格子排成一列，编号为 $1,2,\dots,N$，以及一个长度为 $N$ 的数列 $A=(A_1,A_2,\dots,A_N)$。 最开始，格子 $1$ 被涂成黑色，其余 $N-1$ 个格子为白色，并且有一个棋子放在格子 $1$ 上。

你可以进行如下操作，次数不限（可以为 $0$ 次）：

• 当棋子在格子 $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$。

输出格式

输出一个整数，表示所有可能的黑色格子集合的数量，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

5
1 2 3 1 1

输出 #1

8

输入输出样例 #2

输入 #2

1
200000

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

721419738

说明/提示

限制

• 所有输入均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 2 \times 10^5$

样例解释 1

所有可能的黑色格子集合如下，共有 $8$ 种：

• 格子 $1$
• 格子 $1,2$
• 格子 $1,2,4$
• 格子 $1,2,4,5$
• 格子 $1,3$
• 格子 $1,4$
• 格子 $1,4,5$
• 格子 $1,5$

样例解释 3

注意答案需要对 $998244353$ 取模。

由 ChatGPT 4.1 翻译