← 返回题目列表

AtCoder · abc335_f

I. 跳双六

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

分数: 525 点

问题陈述

有一排 N 标记的方块 1,2,\dots,N 和一个序列 A=(A_1,A_2,\dots,A_N) 长度 N.
最初,正方形 1 涂成黑色,其他 N-1 方格被涂成白色,并在方格上放置一块 1.

您可以重复以下操作任意次数,可能为零:

  • 当棋子在正方形上时 i,选择一个正整数 x 并将棋子移动到正方形 i + A_i \times x.
    • 在这里,你不能用 i + A_i \times x > N.
  • 然后,绘制正方形 i + A_i \times x 黑色。

求在运算结束时可以涂成黑色的可能的方块组的数量,取模 998244353.

约束

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

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N

输出

将答案打印为整数。


示例输入 1

5
1 2 3 1 1

示例输出 1

8

有八组可能的涂成黑色的方块:

  • 广场 1
  • 正方形 1,2
  • 正方形 1,2,4
  • 正方形 1,2,4,5
  • 正方形 1,3
  • 正方形 1,4
  • 正方形 1,4,5
  • 正方形 1,5

示例输入 2

1
200000

示例输出 2

1

示例输入 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

一定要找到模数 998244353.