#P13101. [AGC062E] Overlap Binary Tree

    ID: 12285 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000组合数学多项式FFT生成函数计数DP树形DP构造

[AGC062E] Overlap Binary Tree

题目描述

给定一个奇数 NN 和一个非负整数 KK。

请计算满足以下所有条件的整数对序列 ((L1,R1),(L2,R2),…,(LN,RN))((L_1,R_1),(L_2,R_2),\dots,(L_N,R_N)) 的个数,并对 998244353998244353 取模。

  • (L1,R1,L2,R2,…,LN,RN)(L_1,R_1,L_2,R_2,\dots,L_N,R_N) 是 11 到 2N2N 的一个排列。
  • L1≤L2≤⋯≤LNL_1 \leq L_2 \leq \dots \leq L_N。
  • 对于所有 1≤i≤N1 \leq i \leq N,有 Li≤RiL_i \leq R_i。
  • 恰好有 KK 个 ii 满足 Li+1=RiL_i+1=R_i。
  • 存在一个以 11 到 NN 编号的 NN 个顶点的有根二叉树 TT,满足下述性质:
    • 在 TT 中,顶点 ii 和 jj 存在祖先-子孙关系,当且仅当区间 [Li,Ri][L_i,R_i] 和 [Lj,Rj][L_j,R_j] 有交集。

这里,有根二叉树指的是每个节点的子节点数为 00 或 22 的有根树。在树 TT 中,如果顶点 jj 在连接根和顶点 ii 的简单路径上,或者顶点 ii 在连接根和顶点 jj 的简单路径上,则称顶点 ii 和 jj 存在祖先-子孙关系。

输入格式

输入为一行,包含两个整数:

NN KK

输出格式

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

输入输出样例 #1

输入 #1

3 1

输出 #1

2

输入输出样例 #2

输入 #2

1 0

输出 #2

0

输入输出样例 #3

输入 #3

521 400

输出 #3

0

输入输出样例 #4

输入 #4

199999 2023

输出 #4

283903125

说明/提示

限制条件

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

样例解释 1

例如,(L1,R1)=(1,5),(L2,R2)=(2,3),(L3,R3)=(4,6)(L_1,R_1)=(1,5),(L_2,R_2)=(2,3),(L_3,R_3)=(4,6) 时,只有 i=2i=2 满足 Li+1=RiL_i+1=R_i,即恰好有 11 个。此外,对于第 55 个条件中描述的树,顶点 11 作为根,其子节点为顶点 22 和 33,这样的有根树是满足条件的。