UOJ Logo Universal Online Judge

UOJ

#633. 【UR #21】你将如闪电般归来

统计

在第三个游戏中赢下了小 L 后,跳跳将军放你离开了跳跳堡。

而在长时间围困跳跳堡后,跳蚤国王指挥部队发动了总攻。双方交战异常激烈,最终你立下了大功,利用潜入跳跳堡时得到的地图发现了突破口——一座无人防守的小门,于是潮水般的跳蚤和蛐蛐涌进了小门,跳蚤蛐蛐联军终于成功收复了跳跳堡,恢复了跳蚤国。

在庆功宴上,跳蚤乐队奏响了新谱的歌曲《你将如闪电般归来》,跳蚤国王心情大好,给在场的宾客们出了一个题,只要能做出这个题就可以获得他的大赏:

给定一棵节点被染有红色或绿色的有标号有根树,我们称之为“闪电树”当且仅当:

  1. 每个节点 $i$ 的父亲编号 $p_i$ 比 $i$ 小,即 $p_i < i$;
  2. 这棵树的每一层恰有一个红色节点;
  3. 对于任意一个节点,如果它不是根节点,那么它的父亲一定是红色;
  4. 任意一个红色节点的绿色孩子数量均为偶数个。

“可以推出,闪电树中红色的节点形成了一条从根节点往下连到某个叶子节点的红色路径,就像一条红色的闪电,划开前方的艰难险阻……” 跳蚤国王形象地描述道。

给定 $k, n$,问节点数为 $n$ 层数为 $k$ 的闪电树的数量对 $998244353$ 取模的值。

这道题非常难,在场的其他宾客绞尽脑汁也不知道怎么完成,但你——伏特是一名计算机高手,发现这个题目可以用计算机轻松解决。只要解决了它,大赏就是你的了!

输入格式

一行两个正整数 $k,n$,表示树的层数和结点数。

输出格式

一行一个整数表示答案对 $998244353$ 取模的值。

样例一

input

2 10

output

9

explanation

容易发现树的形态一定只能是 $p_2=p_3=\ldots=p_{10}=1$,即第一层为节点 $1$,第二层为节点 $2\sim 10$。

而对于树的颜色,显然节点 $1$ 只能是红色,节点 $2\sim 10$ 中恰好有一个是红色,其余是绿色,因此共有 $9$ 种方案。

样例二

input

3 7

output

65

样例三

input

8 14

output

703179

样例四

input

529 1453

output

159030840

样例五

input

1453 14530529

output

443513052

样例六

input

10 1000000000000000000

output

384797525

数据范围

对于所有数据,$1\le k\le 10^7$,$k\le n\le 10^{18}$,$k\equiv n \pmod 2$。

子任务编号 $k\le$ $n\le$ 分值
$1$ $n$ $100$ $15$
$2$ $3\times 10^3$ $10$
$3$ $10^5$ $15$
$4$ $10^7$ $10$
$5$ $3$ $10^{18}$ $5$
$6$ $100$ $15$
$7$ $10^3$ $15$
$8$ $10^7$ $15$

时间限制:$2\texttt{s}$

空间限制:$1\texttt{GB}$

下载

样例数据下载