← 返回题目列表

AtCoder · abc215_g

G. 七彩糖果2

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

分数: 600 点

问题陈述

有 N 糖果从左到右排列成一排。
每个糖果都有以下其中一项 10^9 颜色: 颜色 1, 颜色 2, \ldots, 颜色 10^9.
对于每个 i = 1, 2, \ldots, N, i左边第一个糖果有颜色 c_i.

高桥会选择 K 来自 N 糖果并得到那些 K 糖果。
有 \binom{N}{K} 选择方式 K 来自 N 糖果,在哪里 \binom{N}{K} 是二项式系数。高桥会随机选择其中之一 \binom{N}{K} 等概率的方式。

因为高桥想吃彩色糖果,所以他的糖果颜色越多,他就会越高兴。
对于每个场景 K = 1, 2, \ldots, N,求高桥的糖果的不同颜色数量的期望值。
我们可以证明所求的值是一个有理数。打印这个有理数模 998244353,如注释中所述。

注释

打印有理数时,首先将其写为分数 \frac{y}{x},其中 x, y 是整数并且 x 不能被整除 998244353 (在问题的约束下,这种表示总是可能的)。 然后,您需要打印唯一的整数 z 之间 0 和 P - 1,包含在内,满足 xz \equiv y \pmod{998244353}.

约束

  • 1 \leq N \leq 5 \times 10^4
  • 1 \leq c_i \leq 10^9
  • 输入中的所有值都是整数。

输入

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

N
c_1 c_2 \ldots c_N

输出

打印 N 行。的 i- 第行应包含高桥糖果在场景中的不同颜色数量的预期值 K = i,模数 998244353 如注释中所述。


示例输入 1

3
1 2 2

示例输出 1

1
665496237
2

当 K = 1,他将得到 1-st糖果, 2-nd 糖果,或 3-rd 糖果。无论如何,他的糖果都会有一种颜色,因此不同颜色的数量的期望值为 1.

当 K = 2,他将得到 1-st 和 2-nd糖果, 2-nd 和 3-rd 糖果,或 1-st 和 3-rd 糖果。

  • 如果他得到 1-st 和 2-还有糖果,它们有两种不同的颜色。
  • 如果他得到 2-nd 和 3-rd 糖果,它们只有一种颜色。
  • 如果他得到 1-st 和 3-rd糖果,它们有两种不同的颜色。

因此,不同颜色数量的期望值为 \frac{1}{3} \cdot 2 + \frac{1}{3} \cdot 1 + \frac{1}{3} \cdot 2 = \frac{5}{3}.
请务必以模数形式打印 998244353 如注释中所述。

当 K = 3,他总是会得到 1-st, 2-nd,和 3-rd糖果,有两种不同颜色,所以不同颜色数量的期望值为 2.


示例输入 2

11
3 1 4 1 5 9 2 6 5 3 5

示例输出 2

1
725995895
532396991
768345657
786495555
937744700
574746754
48399732
707846002
907494873
7