分数: 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 用于随机均匀选择的堆状排列。
可以证明所求的概率总是有理数。另外,在该问题的约束下,当所求的有理数表示为不可约分数时 \frac{P}{Q},可以证明 Q \neq 0 \pmod{998244353}。因此,存在一个唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353} 和 0 \leq R \lt 998244353。打印此内容 R.概率模的定义 998244353
约束
- 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