AT_agc062_e.[AGC062E] Overlap Binary Tree

给定一个奇数 $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$。
• 对于所有 $1 \leq i \leq N$，有 $L_i \leq R_i$。
• 恰好有 $K$ 个 $i$ 满足 $L_i+1=R_i$。
• 存在一个以 $1$ 到 $N$ 编号的 $N$ 个顶点的有根二叉树 $T$，满足下述性质：
  • 在 $T$ 中，顶点 $i$ 和 $j$ 存在祖先-子孙关系，当且仅当区间 $[L_i,R_i]$ 和 $[L_j,R_j]$ 有交集。

这里，有根二叉树指的是每个节点的子节点数为 $0$ 或 $2$ 的有根树。在树 $T$ 中，如果顶点 $j$ 在连接根和顶点 $i$ 的简单路径上，或者顶点 $i$ 在连接根和顶点 $j$ 的简单路径上，则称顶点 $i$ 和 $j$ 存在祖先-子孙关系。

输入为一行，包含两个整数：

$N$ $K$

输出满足条件的序列个数对 $998244353$ 取模的结果。

限制条件

• $1 \leq N < 2 \times 10^5$
• $0 \leq K \leq N$
• $N$ 是奇数
• 输入的所有值均为整数

样例解释 1

例如，$(L_1,R_1)=(1,5),(L_2,R_2)=(2,3),(L_3,R_3)=(4,6)$ 时，只有 $i=2$ 满足 $L_i+1=R_i$，即恰好有 $1$ 个。此外，对于第 $5$ 个条件中描述的树，顶点 $1$ 作为根，其子节点为顶点 $2$ 和 $3$，这样的有根树是满足条件的。

由 ChatGPT 4.1 翻译