分数: 700 点
问题陈述
Kuro 和 Shiro 正在玩由以下组成的棋盘 n 方块排成一排。 方块已编号 1 to n 从左到右,和广场 s 上有一个标记。
首先,对于每个方块,Kuro 以相同的概率将其漆成黑色或白色,独立于其他方块。然后,他穿上 Square s 一块与正方形颜色相同的石头。
Kuro和Shiro将使用这个棋盘和无限多个黑子和白子来玩游戏。在这场比赛中,黑和白轮流下棋,如下,黑先走:
- 选择一个与上面有石头的方块相邻的空方块。让我们说广场 选择 i 。
- 放在正方形上 i 一块与正方形颜色相同的石头。
- 如果存在 Square 以外的格子 i 包含一个与刚刚放置的石头颜色相同的石头,在这些方块中,让 Square j 是距离 Square 最近的一个 i。改变方块之间每块石头的颜色 i 和广场 j 到 Square 的颜色 i.
当棋盘上没有空格时游戏结束。
Kuro 的最佳玩法是在游戏结束时最大化黑子的数量,而 Shiro 的最佳玩法是在游戏结束时最大化白子的数量。
对于每种情况 s=1,\dots,n,求期望值,取模 998244353,游戏结束时黑子的数量。
注释
当相关期望值表示为不可约分数时 p/q,唯一存在一个整数 r 这样 rq=p ~(\text{mod } 998244353) 和 0 \leq r \lt 998244353,我们要求您找到它。
约束
- 1 \leq n \leq 2\times 10^5
输入
输入由标准输入按以下格式给出:
n
输出
打印 n 值。 的 i-th 值应该是期望值,模 998244353, 该案游戏结束时黑子的数量 s=i.
示例输入 1
3
示例输出 1
499122178 499122178 499122178
让我们使用 b 代表黑色方块并且 w 代表白色方块。
有八种可能的板: www, wwb, wbw, wbb, bww, bwb, bbw,和 bbb,以相同的概率被选择。
对于每个板,都会有 0, 1, 0, 2, 1, 3, 2,和 3 游戏结束时分别为黑子,无论其价值 s。 因此,期望的石子数量为 (0+1+0+2+1+3+2+3)/8 = 3/2,答案是 r = 499122178,满足 2r = 3 ~(\text{mod } 998244353) 和 0 \leq r \lt 998244353.
示例输入 2
10
示例输出 2
5 5 992395270 953401350 735035398 735035398 953401350 992395270 5 5
示例输入 3
19
示例输出 3
499122186 499122186 499110762 499034602 498608106 496414698 485691370 434999274 201035754 138645483 201035754 434999274 485691370 496414698 498608106 499034602 499110762 499122186 499122186