A1778. 方格染色
编程题
提高+/省选-
知识点
题目描述
时间限制：2500ms
内存限制：512MB
有 $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 \gt N$。
- 然后将方格 $i + A_i \times x$ 涂黑。
求在操作结束时可以涂黑的方格的集合数，由于这个数字很大，请将答案对 $998244353$ 取模。
内存限制：512MB
有 $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 \gt N$。
- 然后将方格 $i + A_i \times x$ 涂黑。
求在操作结束时可以涂黑的方格的集合数，由于这个数字很大，请将答案对 $998244353$ 取模。
输入格式
每个测试点包含多个测试用例。第一行为测试用例的总数 $t(1 \le t \le 5)$。
每个测试用例的第一行为方格的总数 $N(1 \le N \le 2 \times 10^5)$。
每个测试用例的第 $2$ 行有 $N$ 个整数 $A_i(1 \le A_i \le 2 \times 10^5)$ 表示序列 $A$。
每个测试用例的第一行为方格的总数 $N(1 \le N \le 2 \times 10^5)$。
每个测试用例的第 $2$ 行有 $N$ 个整数 $A_i(1 \le A_i \le 2 \times 10^5)$ 表示序列 $A$。
输出格式
对于每个测试用例在单独的一行中输出答案。
输入输出样例
输入 #1
3 5 1 2 3 1 1 1 200000 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
输出 #1
8 1 721419738
说明/提示
对于第一个测试用例：
有八组染色的可能：
- 方格 $1$
- 方格 $1,2$
- 方格 $1,2,4$
- 方格 $1,2,4,5$
- 方格 $1,3$
- 方格 $1,4$
- 方格 $1,4,5$
- 方格 $1,5$
有八组染色的可能：
- 方格 $1$
- 方格 $1,2$
- 方格 $1,2,4$
- 方格 $1,2,4,5$
- 方格 $1,3$
- 方格 $1,4$
- 方格 $1,4,5$
- 方格 $1,5$