問題一覧 > 通常問題

No.1608 Yet Another Ants Problem

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 : SPD_9X2SPD_9X2 / テスター : cloudman_Pcloudman_P penguinmanpenguinman
8 ProblemId : 6479 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-17 00:47:08

問題文

長さ $L$ センチメートルの棒があります。例のごとく、この棒の上には $N$ 匹の蟻がいます。

最初、左から $i$ 番目の蟻は、棒の左端から $A_i$ センチメートルの位置にいます。 $2$ 匹以上の蟻が同じ位置にいることはありません。

蟻は、合図と同時にあらかじめ指示された方向(左右どちらか)に $1$ センチメートル/秒 の速さで動き始めます。

蟻同士が棒の上で出会うと、即座に向きを反転して再び歩き始めます。

蟻は棒の左右どちらかの端に到達すると、棒から落ちてしまいます。


蟻はまだ最初の進行方向を指示されていません。あなたは今から各蟻に移動開始時に左右のどちらに進むかの指示を与え、その後に合図を出します。

指示の与え方は $2^N$ 通りあります。全ての指示の与え方の中で、最初に左から $i$ 番目にいた蟻が最後に棒から落ちる場合の数を $998244353$ で割った余りを各 $i$ に関して求めてください。

ただし、最後に左右端から別々の蟻が同時に落ちてしまった場合、棒の左端から落ちた蟻を最後に棒から落ちたとみなします。

入力

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

  • 入力は全て整数。
  • $1 \le N \le 3000$
  • $2 \le L \le 10^9$
  • $1 \le A_1 <\ ... <\ A_i <\ A_{i+1} <\ ... <\ A_N <\ L$

出力

$N$ 行出力してください。
$i$ 行目には、最初に左から $i$ 番目にいた蟻が最後に棒から落ちる場合の数を $998244353$ で割った余りを出力し、改行してください。

サンプル

サンプル1
入力
2 10
3 7
出力
3
1

$1,2$ 人目の向きが、それぞれ
左左 のとき、 $2$ 人目が最後に落ちます。
左右 のとき、 同時に落ちますが、左に落ちるのは $1$ 人目です。
右左 のとき、同時に落ちますが、左に落ちるのは $1$ 人目です。
右右 のとき、$1$ 人目が最後に落ちます。

サンプル2
入力
4 10
1 2 3 4
出力
1
4
6
5

サンプル3
入力
10 100
1 12 34 47 55 56 70 88 91 94
出力
1
13
64
169
259
257
169
72
18
2

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