C - Large Heap Editorial /

Time Limit: 10 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

(1,2,\cdots,2^N-1) の順列 P=(P_1,P_2,\cdots,P_{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 とします．

ヒープ的な順列を一様ランダムに 1 つ選んだ際，P_U<P_V である確率を \text{mod }998244353 で求めてください．

確率 \text{mod }{998244353} の定義

求める確率は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、求める有理数を既約分数 \frac{P}{Q} で表した時、Q \neq 0 \pmod{998244353} となることが証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 を満たす整数 R が一意に定まります。 この 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) の 2 つです． P_2<P_3 となる確率は 1/2 です．

入力例 2

3 1 2

出力例 2

124780545

入力例 3

4 3 2

出力例 3

260479386

入力例 4

2022 12 25

出力例 4

741532295

Score : 800 points

Problem Statement

Consider a permutation P=(P_1,P_2,\cdots,P_{2^N-1}) of (1,2,\cdots,2^N-1). P is said to be heaplike if and only if all of the following conditions are satisfied.

  • 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)

You are given integers A and B. Let U=2^A and V=2^{B+1}-1.

Find the probability, modulo 998244353, that P_U<P_V for a heaplike permutation chosen uniformly at random.

Definition of probability modulo 998244353

It can be proved that the sought probability is always rational. Additionally, under the constraints of this problem, when the sought rational number is represented as an irreducible fraction \frac{P}{Q}, it can be proved that Q \neq 0 \pmod{998244353}. Therefore, there is a unique integer R such that R \times Q \equiv P \pmod{998244353} and 0 \leq R \lt 998244353. Print this R.

Constraints

  • 2 \leq N \leq 5000
  • 1 \leq A,B \leq N-1
  • All numbers in the input are integers.

Input

The input is given from Standard Input in the following format:

N A B

Output

Print the answer.

Sample Input 1

2 1 1

Sample Output 1

499122177

There are two heaplike permutations: P=(1,2,3),(1,3,2). The probability that P_2<P_3 is 1/2.

Sample Input 2

3 1 2

Sample Output 2

124780545

Sample Input 3

4 3 2

Sample Output 3

260479386

Sample Input 4

2022 12 25

Sample Output 4

741532295