E - Overlap Binary Tree Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 1300

問題文

奇数 N 、および非負整数 K が与えられます。

以下の条件をすべて満たす整数の組の列 ((L_1,R_1),(L_2,R_2),\dots,(L_N,R_N)) の数を 998244353 で割った余りを求めてください。

  • (L_1,R_1,L_2,R_2,\dots,L_N,R_N)1 から 2N までの整数の順列
  • L_1 \leq L_2 \leq \dots \leq L_N
  • L_i \leq R_i \ (1 \leq i \leq N)
  • L_i+1=R_i が成り立つような i\ (1\leq i \leq N) はちょうど K 個存在する
  • 1 から N までの番号が付いた N 頂点の根付き二分木 T であって、以下が成り立つものが存在する
    • T において頂点 i,j には祖先・子孫の関係がある \iff 区間 [L_i,R_i],[L_j,R_j] が共通部分を持つ

ただし、根付き二分木とは、全ての頂点の子の個数が 0 個か 2 個であるような根付き木のことを指します。また、木 T において頂点 j が根と頂点 i を結ぶ単純パス上に存在する、または頂点 i が根と頂点 j を結ぶ単純パス上に存在するとき、T において頂点 i,j には祖先・子孫の関係があるといいます。

制約

  • 1 \leq N < 2 \times 10^5
  • 0 \leq K \leq N
  • N は奇数
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

N K

出力

答えを出力してください。


入力例 1

3 1

出力例 1

2

例えば (L_1,R_1)=(1,5),(L_2,R_2)=(2,3),(L_3,R_3)=(4,6) の場合、L_i+1=R_i が成り立つのは i=21 個のみです。また、5 番目の条件で述べられている木については、頂点 1 が根であり、その子が頂点 2,3 であるような根付き木が該当します。


入力例 2

1 0

出力例 2

0

入力例 3

521 400

出力例 3

0

入力例 4

199999 2023

出力例 4

283903125

Score: 1300 points

Problem Statement

You are given an odd number N and a non-negative integer K.

Find the number, modulo 998244353, of sequences of integer pairs ((L_1,R_1),(L_2,R_2),\dots,(L_N,R_N)) satisfying all of the following conditions.

  • (L_1,R_1,L_2,R_2,\dots,L_N,R_N) is a permutation of the integers from 1 to 2N.
  • L_1 \leq L_2 \leq \dots \leq L_N.
  • L_i \leq R_i \ (1 \leq i \leq N).
  • There are exactly K indices i\ (1\leq i \leq N) such that L_i+1=R_i.
  • There is a rooted binary tree T with N vertices numbered from 1 to N such that the following holds:
    • vertices i and j have an ancestor-descendant relationship in T \iff intervals [L_i,R_i] and [L_j,R_j] intersect.

Here, a rooted binary tree is a rooted tree where each vertex has 0 or 2 children. Vertices i and j are said to have an ancestor-descendant relationship in a tree T if either vertex j exists on the simple path connecting the root to vertex i, or vice versa.

Constraints

  • 1 \leq N < 2 \times 10^5
  • 0 \leq K \leq N
  • N is odd.
  • All input values are integers.

Input

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

N K

Output

Print the answer.


Sample Input 1

3 1

Sample Output 1

2

For example, if (L_1,R_1)=(1,5),(L_2,R_2)=(2,3),(L_3,R_3)=(4,6), then i=2 is the only pair with L_i+1=R_i. Also, the fifth condition is satisfied by a tree where vertex 1 is the root, and its children are vertices 2 and 3.


Sample Input 2

1 0

Sample Output 2

0

Sample Input 3

521 400

Sample Output 3

0

Sample Input 4

199999 2023

Sample Output 4

283903125