問題一覧 > 通常問題

No.1608 Yet Another Ants Problem

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 46
作問者 : SPD_9X2 / テスター : penguinman むかで
お気に入りにしたユーザー ProblemId : 6479 / 自分の提出
問題文最終更新日: 2021-07-17 00:47:08
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 304 (順位表) の他の問題:

Problem Statement

There is a stick of length $L$ centimeters. As usual, there are $N$ ants on this stick.

Initially, the $i$-th ant from the left is at a position $A_i$ centimeters from the left end of the stick. No $2$ or more ants are at the same position.

At a signal, each ant starts moving in its pre-instructed direction (either left or right) at a speed of $1$ centimeter/second.

When ants meet each other on the stick, they immediately reverse direction and start walking again.

When an ant reaches either the left or right end of the stick, it falls off the stick.


The ants have not yet been instructed on their initial directions of travel. You will now give each ant an instruction on whether to go left or right when it starts moving, and then give the signal.

There are $2^N$ ways to give the instructions. For each $i$, among all the ways to give the instructions, find the number of ways in which the ant initially $i$-th from the left is the last to fall off the stick, modulo $998244353$.

However, if at the very end different ants fall off the left and right ends simultaneously, the ant that fell off the left end of the stick is considered to be the last to fall off the stick.

Input

$N\ L$
$A_1\ ... A_N$

  • All inputs are integers.
  • $1 \le N \le 3000$
  • $2 \le L \le 10^9$
  • $1 \le A_1 <\ ... <\ A_i <\ A_{i+1} <\ ... <\ A_N <\ L$

Output

Output $N$ lines.
On the $i$-th line, output the number of ways in which the ant initially $i$-th from the left is the last to fall off the stick, modulo $998244353$, followed by a newline.

Sample

Sample 1
Input
2 10
3 7
Output
3
1

When the directions of ants $1,2$ are, respectively,
left, left: ant $2$ falls last.
left, right: they fall simultaneously, but the one falling to the left is ant $1$.
right, left: they fall simultaneously, but the one falling to the left is ant $1$.
right, right: ant $1$ falls last.

Sample 2
Input
4 10
1 2 3 4
Output
1
4
6
5

Sample 3
Input
10 100
1 12 34 47 55 56 70 88 91 94
Output
1
13
64
169
259
257
169
72
18
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。