← 返回题目列表

AtCoder · arc109_e

E. 一维黑白棋生成器

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

Kuro 和 Shiro 正在玩由以下组成的棋盘 n 方块排成一排。 方块已编号 1 to n 从左到右,和广场 s 上有一个标记。

首先,对于每个方块,Kuro 以相同的概率将其漆成黑色或白色,独立于其他方块。然后,他穿上 Square s 一块与正方形颜色相同的石头。

Kuro和Shiro将使用这个棋盘和无限多个黑子和白子来玩游戏。在这场比赛中,黑和白轮流下棋,如下,黑先走:

  1. 选择一个与上面有石头的方块相邻的空方块。让我们说广场 选择 i 。
  2. 放在正方形上 i 一块与正方形颜色相同的石头。
  3. 如果存在 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