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