AtCoder Grand Contest 062
E
Overlap Binary Tree
AtCoder
⌀ 4233
原题
← DF →
翻译中…

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.

翻译中…

样例

Input #1
3 1
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$.
Input #2
1 0
Output #2
0
Input #3
521 400
Output #3
0
Input #4
199999 2023
Output #4
283903125
题目信息
题号
agc062_e
时间限制
8 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。