Score : $525$ points

问题描述

有一行 $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$ 取模。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a row of $N$ squares labeled $1,2,\dots,N$ and a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$.
Initially, square $1$ is painted black, the other $N-1$ squares are painted white, and a piece is placed on square $1$.

You may repeat the following operation any number of times, possibly zero:

• When the piece is on square $i$, choose a positive integer $x$ and move the piece to square $i + A_i \times x$.
  • Here, you cannot make a move with $i + A_i \times x > N$.
• Then, paint the square $i + A_i \times x$ black.

Find the number of possible sets of squares that can be painted black at the end of the operations, modulo $998244353$.

Constraints

• All input values are integers.
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 2 \times 10^5$

Input

The input is given from Standard Input in the following format:

$N$

$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the answer as an integer.

Sample Input 1

5
1 2 3 1 1

Sample Output 1

8

There are eight possible sets of squares painted black:

• Square $1$
• Squares $1,2$
• Squares $1,2,4$
• Squares $1,2,4,5$
• Squares $1,3$
• Squares $1,4$
• Squares $1,4,5$
• Squares $1,5$

Sample Input 2

1
200000

Sample Output 2

1

Sample Input 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

Sample Output 3

721419738

Be sure to find the number modulo $998244353$.

update @ 2024/3/10 01:24:31