← 返回题目列表

AtCoder · abc428_g

G. 项链

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

分数: 625 点

问题陈述

有 N 珠宝类型编号为 1 to N。您拥有无限数量的各种类型的珠宝。同一类型的珠宝是无法区分的。
另外,还有一个整数 U 即 2 或更大。每颗宝石的美丽度由一个介于 2 和 U,包容,珠宝之美 i is b_i.

对于每个整数 x 满意 2 \leq x \leq U,让 f(x) 是以下问题的答案:

您将把一些珠宝排列成圆形图案来制作项链。
求模数 998244353,项链的所使用的珠宝的美丽的产品等于 x.
此处,两条项链被认为是相同的,并且如果旋转后匹配,则仅计数一次。然而,如果两条项链仅通过旋转不匹配,即使颠倒旋转后匹配,也将单独计算。例如,请考虑以下情况:

  • 项链A:由宝石排列而成的项链 1, 2, 3 按顺时针顺序。
  • 项链B:宝石排列而成的项链 2, 3, 1 按顺时针顺序。
  • 项链C:宝石排列而成的项链 1, 3, 2 按顺时针顺序。

这里,项链A和B被认为是相同的并且只计算一次,但是项链A和C是分开计算的。

计算 f(2), f(3), \dots, f(U).

约束

  • 1 \leq N \leq 5 \times 10^5
  • 2 \leq U \leq 5 \times 10^5
  • 2 \leq b_i \leq U
  • 所有输入值均为整数。

输入

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

N U
b_1 b_2 \dots b_N

输出

输出 f(2), f(3), \dots, f(U) 一行中以空格分隔。


示例输入 1

4 6
2 2 3 4

示例输出 1

2 1 4 0 2

例如,当 x=4,以下四条项链满足条件:

  • 由宝石排列而成的项链 1, 1 按顺时针顺序。
  • 由宝石排列而成的项链 1, 2 按顺时针顺序。
  • 由宝石排列而成的项链 2, 2 按顺时针顺序。
  • 宝石排列而成的项链 4.

示例输入 2

4 16
2 2 2 2

示例输出 2

4 0 10 0 0 0 24 0 0 0 0 0 0 0 70

示例输入 3

14 12
10 2 2 3 8 7 11 6 12 4 9 5 3 2

示例输出 3

3 2 7 1 7 1 15 4 4 1 24