← 返回题目列表

AtCoder · ndpc2026_l

L. 液晶模组

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

分数: 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