#308. 星辰遗迹

星辰遗迹

题目描述

在广阔无垠的宇宙中,存在着一座神秘的星辰遗迹,其中隐藏着通往至高智慧的远古星图。传说中,只有那些能够精确排列星光碎片的人,才能揭示遗迹的最终奥秘。

你是一名探索者,被选中前往这座遗迹,任务是使用 NN 颗星光碎片,以特定的方式排列它们的光辉强度,使得它们汇聚后的总星辉刚好等于 KK,从而激活星图。然而,遗迹的能量法则十分特殊,只有遵循特定规则的星光排列方式,才能形成稳定的星辉阵列。

每一颗星光碎片的光辉强度只能是某种基本光辉单位的 2i2^i,即可选的值只能是:

1,12,14,18,1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \dots

其中 ii 可以是任意非负整数。

你的任务是计算有多少种不同的排列方式可以使用恰好 NN 颗星光碎片,使它们的总星辉恰好等于 KK,并且所有碎片的光辉强度均符合遗迹的能量法则。

由于可能的排列方式很多,请将答案对 998244353998244353 取模后输出。

星辉排列规则

  1. 星光碎片的数量限制

    • 每种合法的星辉阵列都必须由恰好 NN 颗星光碎片组成,不能多也不能少。
  2. 总星辉的要求

    • NN 颗星光碎片的总光辉必须严格等于 KK
  3. 可用的星光强度

    • 每一颗星光碎片的光辉必须是 1,12,14,18,1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, … 中的某一个值,即它们只能表示为 12i\frac{1}{2^i}(其中 i0i \geq 0)。
  4. 排列方式

    • 星光碎片的排列顺序不影响最终的星辉阵列的数量。

输入格式

输入包含两个整数 NNKK,分别表示:

  • NN(用于排列的星光碎片数量)
  • KK(目标星辉总量)

输出格式

输出一个整数,表示符合所有要求的星辉阵列的数量,结果对 998244353998244353 取模。

数据范围

  • 1KN30001 \leq K \leq N \leq 3000

样例

4 2
2
2525 425
687232272

解释

对于样例1:

在此情况下,符合要求的星辉排列有:

  1. (1,12,14,14)(1, \frac{1}{2}, \frac{1}{4}, \frac{1}{4})
  2. $(\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2})$

这两种方法都满足:

  • 数量:刚好 4 颗星光碎片。
  • 总星辉:严格等于 2。
  • 碎片强度:所有星光碎片均符合 12i\frac{1}{2^i} 形式。