分数: 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