/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 550 点
問題文
N 人の人が一列に並んでおり、人 i は先頭から i 番目に並んでいます。
以下の操作を、列に並んでいる人が 1 人になるまで繰り返します。
- 先頭に並んでいる人を \frac{1}{2} の確率で列から取り除き、そうでない場合は列の末尾に移す。
人 i=1,2,\ldots,N それぞれについて、人 i が最後まで列に並んでいる 1 人になる確率を \text{mod }998244353 で求めて下さい。(取り除くかどうかの選択はすべてランダムかつ独立です。)
確率 \text{mod } 998244353 の定義
この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが保証されます。
このとき xz \equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。
制約
- 2\leq N\leq 3000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
人 i=1,2,\ldots,N に対する答えを空白区切りで出力せよ。
入力例 1
2
出力例 1
332748118 665496236
人 1 が最後まで列に並んでいる 1 人になる確率は \frac{1}{3} です。
人 2 が最後まで列に並んでいる 1 人になる確率は \frac{2}{3} です。
入力例 2
5
出力例 2
235530465 792768557 258531487 238597268 471060930
Score : 550 points
Problem Statement
There are N people standing in a line, with person i standing at the i-th position from the front.
Repeat the following operation until there is only one person left in the line:
- Remove the person at the front of the line with a probability of \frac{1}{2}, otherwise move them to the end of the line.
For each person i=1,2,\ldots,N, find the probability that person i is the last person remaining in the line, modulo 998244353. (All choices to remove or not are random and independent.)
How to find probabilities modulo 998244353
The probabilities sought in this problem can be proven to always be a rational number. Furthermore, the constraints of this problem guarantee that if the sought probability is expressed as an irreducible fraction \frac{y}{x}, then x is not divisible by 998244353.
Now, there is a unique integer z between 0 and 998244352, inclusive, such that xz \equiv y \pmod{998244353}. Report this z.
Constraints
- 2\leq N\leq 3000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer for people i=1,2,\ldots,N, separated by spaces.
Sample Input 1
2
Sample Output 1
332748118 665496236
Person 1 will be the last person remaining in the line with probability \frac{1}{3}.
Person 2 will be the last person remaining in the line with probability \frac{2}{3}.
Sample Input 2
5
Sample Output 2
235530465 792768557 258531487 238597268 471060930