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