/ 
実行時間制限: 8 sec / メモリ制限: 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=2 の 1 個のみです。また、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