← 返回题目列表

AtCoder · abc333_f

I. 炸弹游戏 2

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

分数: 550 点

问题陈述

有 N 人们排成一排,有人 i 站在 i从前面数第一个位置。

重复以下操作,直到队伍中只剩下一个人:

  • 移除队伍前面的人,概率为 \frac{1}{2},否则将它们移动到行尾。

对于每个人 i=1,2,\ldots,N,求那个人的概率 i 是队列中剩余的最后一个人,取模 998244353。 (所有删除或不删除的选择都是随机且独立的。)

如何求模概率 998244353

可以证明此问题中寻求的概率始终是有理数。此外,该问题的约束保证如果所寻求的概率表示为不可约分数 \frac{y}{x},那么 x 不能被整除 998244353.

现在,有一个唯一的整数 z 之间 0 和 998244352,包含在内,这样 xz \equiv y \pmod{998244353}。报告此事 z.

约束

  • 2\leq N\leq 3000
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N 

输出

为人们打印答案 i=1,2,\ldots,N,用空格分隔。


示例输入 1

2

示例输出 1

332748118 665496236

人 当他们的编程技能达到时, 1 将有概率成为队伍中最后一个人 \frac{1}{3}.

人 当他们的编程技能达到时, 2 将有概率成为队伍中最后一个人 \frac{2}{3}.


示例输入 2

5

示例输出 2

235530465 792768557 258531487 238597268 471060930