AT_abc333_f [ABC333F] Bomb Game 2

题目描述

有 $N$ 个人排成一列，第 $i$ 个人站在队列的第 $i$ 个位置。

重复以下操作，直到队列中只剩下 $1$ 个人为止：

• 以 $\frac{1}{2}$ 的概率将队首的人移出队列，否则将其移到队尾。

对于每个人 $i=1,2,\ldots,N$，请计算第 $i$ 个人成为最后剩下的那个人的概率，并对 $998244353$ 取模输出。（每次是否移除是独立且等概率的。）

概率 $\bmod\ 998244353$ 的定义：本题中要求的概率一定是有理数。并且在本题的约束下，若将概率表示为最简分数 $\frac{y}{x}$，则 $x$ 保证不会被 $998244353$ 整除。

此时，存在唯一的整数 $z$，满足 $0 \leq z \leq 998244352$ 且 $xz \equiv y \pmod{998244353}$。请输出这个 $z$。

输入格式

输入为以下格式，从标准输入读取：

$N$

输出格式

请输出 $i=1,2,\ldots,N$ 每个人的答案，用空格分隔。

输入输出样例 #1

输入 #1

2

输出 #1

332748118 665496236

输入输出样例 #2

输入 #2

5

输出 #2

235530465 792768557 258531487 238597268 471060930

说明/提示

约束

• $2 \leq N \leq 3000$
• 输入均为整数

样例解释 1

第 $1$ 个人成为最后剩下的那个人的概率是 $\frac{1}{3}$。第 $2$ 个人成为最后剩下的那个人的概率是 $\frac{2}{3}$。

由 ChatGPT 4.1 翻译