← 返回题目列表

AtCoder · arc177_d

D. 地震

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

分数: 700 点

问题陈述

AtCoder Street 是一条在平地上用直线表示的道路。有 N 电线杆的高度 H 站在这条路上。柱子有编号 1, 2, \dots, N 按时间顺序排列。杆 i (1 \leq i \leq N) 垂直定位在坐标处 X_i. 每个杆的底座都固定在地面上。 假设两极足够细。

街头必体验 N 地震。期间 i第次地震 (1 \leq i \leq N),发生以下事件:

  1. 如果极 i 还没有落下,它落到数轴上的左边或者右边,各有一个概率 \frac{1}{2}.
  2. 如果掉落的杆子与另一根尚未掉落的杆子相撞(包括杆子底部的碰撞),则后者也会以相同的方向掉落。这可能会引发连锁反应。

在步骤 1 中,一根杆子下落的方向与其他杆子下落的方向无关。

下图是一次地震期间电线杆可能如何倒塌的示例:

对于地震准备,对于每个 t = 1, 2, \dots, N,求所有极点完全下降的概率 t第 次地震。乘以 2^N 并打印结果模数 998244353。可以证明,要打印的值是整数。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq H \leq 10^9
  • 0 \leq X_i \leq 10^9 \ (1 \leq i \leq N)
  • X_1, X_2, \dots, X_N 都是不同的。
  • 所有输入值均为整数。

输入

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

N H
X_1 X_2 \cdots X_N

输出

打印以下问题的答案 t = 1, 2, \dots, N 按此顺序,用空格分隔。


示例输入 1

3 2
0 3 1

示例输出 1

4 2 2

下图显示了此示例输入的极点下降的可能方式。图中的分数表示每种状态发生的概率。

因此,所有极点都下降的概率恰好为 1-st, 2-nd, 3-rd 地震是 分别为 \frac{1}{2}, \frac{1}{4}, \frac{1}{4}。将这些乘以 8 得到 4, 2, 2 用于输出。


示例输入 2

4 10
10 55 20 45

示例输出 2

0 4 4 8

下图显示了此示例输入的极点下降的可能方式。图中的分数表示每种状态发生的概率。

因此,所有极点都下降的概率恰好为 1-st, 2-nd, 3-rd, 4第 次地震是 0, \frac{1}{4}, \frac{1}{4}, \frac{1}{2}。将这些乘以 16 得到 0, 4, 4, 8 用于输出。


示例输入 3

8 1
5 0 6 3 8 1 7 2

示例输出 3

0 64 32 48 24 28 28 32

所有极点完全下降的概率 1-st, 2-nd, 3-rd, 4-th, 5-th, 6-th, 7-th, 8第 次地震是 0, \frac{1}{4}, \frac{1}{8}, \frac{3}{16}, \frac{3}{32}, \frac{7}{64}, \frac{7}{64}, \frac{1}{8}。


示例输入 4

40 20
695 793 11 502 114 861 559 4 212 609 894 435 429 94 91 258 161 45 33 605 673 634 629 163 283 826 409 84 507 548 31 248 588 340 357 168 926 949 322 912

示例输出 4

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 41942627 41942627 360709869

并非所有电线杆都会因 37第 次地震。所有极点完全下降的概率 38, 39, 40第 次地震是 \frac{3}{8}, \frac{3}{8}, \frac{1}{4}。