分数: 5 点
问题陈述
给你一个正整数 N 和排列 A = (A_1, A_2, \dots, A_N) of (1, 2, \dots, N).
考虑一个有向图 G 与 N 顶点编号自 1 to N。对于每对整数 (i, j) 这样 1 \leq i < j \leq N,有 \mathrm{LCM}(A_i, A_j) 从顶点开始的有向边 i 到顶点 j。 (这里, \mathrm{LCM} 表示最小公倍数。)中没有其他边 G.
对于每个 v = 2, 3, \dots, N,查找从顶点开始的路径数 1 到顶点 v,模数 998244353。在这里,如果两条路径经过的边集不同,则认为它们是不同的。
约束
- 2 \leq N \leq 2 \times 10^5
- (A_1, A_2, \dots, A_N) 是一个排列 (1, 2, \dots, N)
- 所有输入值均为整数
输入
输入由标准输入给出,格式如下:
N A_1 A_2 \dots A_N
输出
打印 N-1 行。上 i第行,输出答案 v = i+1.
示例输入 1
4 3 2 1 4
示例输出 1
6 15 96
有向边 G 如下:
- 从顶点 1 到顶点 2: 6 边缘
- 从顶点 1 到顶点 3: 3 边缘
- 从顶点 1 到顶点 4: 12 边缘
- 从顶点 2 到顶点 3: 2 边缘
- 从顶点 2 到顶点 4: 4 边缘
- 从顶点 3 到顶点 4: 4 边缘
示例输入 2
13 12 3 2 4 10 9 5 8 1 6 11 7 13
示例输出 2
12 84 492 11100 1018368 45948480 913466263 559040529 720204824 935993195 339767199 889449065