AT_arc109_e.[ARC109E] 1D Reversi Builder

黒石さん和白石さん正在用一个由 $n$ 个格子排成一行的棋盘进行游戏。每个格子依次编号为 $1$ 到 $n$，其中第 $s$ 个格子上有一个标记。

首先，黒石さん会对每个格子独立地以相等概率选择涂成黑色或白色。然后，在第 $s$ 个格子上放置与该格子颜色相同的棋子。

接下来，黒石さん和白石さん利用这个棋盘以及无限多的黑色棋子和白色棋子进行游戏。游戏规则如下，黒石さん先手，双方轮流进行如下操作：

1. 选择一个与已有棋子相邻的空格子，假设选择了第 $i$ 个格子。
2. 在第 $i$ 个格子上放置与该格子颜色相同的棋子。
3. 如果除第 $i$ 个格子外，棋盘上还存在与新放置棋子颜色相同的棋子，则将第 $i$ 个格子与最近的同色棋子之间所有棋子的颜色都变为第 $i$ 个格子的颜色。

当棋盘上没有空格子时，游戏结束。

黒石さん会采取最优策略使得游戏结束时黑色棋子的数量最大化，白石さん则会采取最优策略使得白色棋子的数量最大化。

请对于 $s=1,\dots,n$ 的每一种情况，求出游戏结束时黑色棋子的数量的期望值，并对 $998244353$ 取模输出。

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

$n$

请输出 $n$ 个值，第 $i$ 个值表示当 $s=i$ 时，游戏结束时黑色棋子的数量的期望值，对 $998244353$ 取模。

注意

若所求期望值可表示为既约分数 $p/q$，则满足 $rq\equiv p\pmod{998244353}$ 且 $0\leq r<998244353$ 的整数 $r$ 在本题的约束下是唯一确定的。这个 $r$ 即为所求答案。

约束条件

• $1\leq n\leq 2\times 10^5$

样例解释 1

用 b 表示黑格，用 w 表示白格。棋盘的所有可能状态有 $8$ 种：www、wwb、wbw、wbb、bww、bwb、bbw、bbb，每种状态被等概率选中。无论 $s$ 取何值，对于每种状态，游戏结束时黑色棋子的数量分别为 $0,1,0,2,1,3,2,3$。因此，期望值为 $(0+1+0+2+1+3+2+3)/8=3/2$，所以答案为满足 $2r\equiv 3\pmod{998244353}$ 且 $0\leq r<998244353$ 的 $r=499122178$。

由 ChatGPT 4.1 翻译