No.1608 Yet Another Ants Problem
タグ : / 解いたユーザー数 46
作問者 :
SPD_9X2
/ テスター :
penguinman
むかで
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もしくは右上の雲マークをクリックしてアカウントを作成してください。