← 返回题目列表

AtCoder · agc060_c

C. 大堆

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

分数: 800 点

问题陈述

考虑一个排列 P=(P_1,P_2,\cdots,P_{2^N-1}) of (1,2,\cdots,2^N-1). P 据说是 堆状 当且仅当满足以下所有条件时。

  • P_i < P_{2i} (1 \leq i \leq 2^{N-1}-1)
  • P_i < P_{2i+1} (1 \leq i \leq 2^{N-1}-1)

给你整数 A 和 B。 让 U=2^A 和 V=2^{B+1}-1.

求概率,模 998244353,即 P_U<P_V 用于随机均匀选择的堆状排列。

概率模的定义 998244353

可以证明所求的概率总是有理数。另外,在该问题的约束下,当所求的有理数表示为不可约分数时 \frac{P}{Q},可以证明 Q \neq 0 \pmod{998244353}。因此,存在一个唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353} 和 0 \leq R \lt 998244353。打印此内容 R.

约束

  • 2 \leq N \leq 5000
  • 1 \leq A,B \leq N-1
  • 输入中的所有数字均为整数。

输入

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

N A B

输出

打印答案。


示例输入 1

2 1 1

示例输出 1

499122177

有两种堆状排列: P=(1,2,3),(1,3,2)。 的概率 P_2<P_3 is 1/2.


示例输入 2

3 1 2

示例输出 2

124780545

示例输入 3

4 3 2

示例输出 3

260479386

示例输入 4

2022 12 25

示例输出 4

741532295