103335: [Atcoder]ABC333 F - Bomb Game 2
Description
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
Output
分数：550分
问题描述
有N个人站成一排，第i个人站在离队伍前面i个位置。
重复以下操作，直到队伍中只剩一个人：
- 以1/2的概率删除队伍前面的人，否则将他们移动到队伍的末尾。
对于每个人i=1,2,…,N，找出第i个人是最后剩下的那人的概率，对998244353取模。（所有的删除或不删除的选择都是随机且独立的。）
如何对998244353取模求概率
本问题中寻求的概率可以被证明总是有理数。此外，本问题的约束保证了如果所寻求的概率表示为不可约分数y/x，则x不被998244353整除。
现在，存在一个整数z，范围在0到998244352之间，包括两端，满足xz ≡ y （mod 998244353）。报告这个z。
约束条件
- 2≤N≤3000
- 所有输入值都是整数。
输入
输入是通过标准输入以以下格式给出的：
$N$
输出
以空格分隔的方式打印出i=1,2,…,N的人的答案。
样例输入1
2
样例输出1
332748118 665496236
第1个人将最后剩下，概率为1/3。
第2个人将最后剩下，概率为2/3。
样例输入2
5
样例输出2
235530465 792768557 258531487 238597268 471060930