← 返回题目列表

AtCoder · past202206_m

M. 逆转

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

分数: 6 点

问题陈述

高桥和青木将进行一场比赛,谁先获胜 N 比赛获胜。两名选手技术相当,并且各自以概率赢得一场比赛 \frac{1}{2},与其他游戏的结果无关。没有平局。

当赢得更多胜利的玩家在两场比赛中发生变化时,就会发生逆转,例如从 2-1 to 2-3 (现在青木领先)。

求直到一名玩家赢得比赛为止逆转次数的期望值,取模 998244353 (见注释)。

注释

可以证明所求的期望值是一个有理数。此外,在该问题的约束下,当该值表示为 \frac{P}{Q} 使用两个互质整数 P 和 Q,可以证明唯一存在一个整数 R 这样 R \times Q \equiv P\pmod{998244353} 和 0 \leq R \lt 998244353。找到这个 R.

约束

  • 2 \leq N \leq 10^7
  • 输入中的所有值都是整数。

输入

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

N

输出

打印期望值模 998244353.


示例输入 1

2

示例输出 1

748683265

仅以下两种情况出现一次反转,其他情况均无反转。

  • 高桥获胜,然后青木获胜,然后青木获胜。
  • 青木获胜,然后高桥获胜,然后高桥获胜。

它们中的每一个都有概率出现 \frac{1}{8},所以寻求的期望值为 \frac{1}{4}.

我们有 748683265 \times 4 \equiv 1\pmod{998244353},所以打印 748683265.


示例输入 2

4

示例输出 2

405536769

示例输入 3

621998

示例输出 3

76706976