AT_abc220_e [ABC220E] Distance on Large Perfect Binary Tree

题目描述

有一棵包含 $2^N-1$ 个顶点的树。
每个顶点编号为 $1$ 到 $2^N-1$，对于每个 $1\leq i < 2^{N-1}$，有如下无向边：

• 连接顶点 $i$ 和顶点 $2i$ 的无向边
• 连接顶点 $i$ 和顶点 $2i+1$ 的无向边

除此之外，没有其他边。

定义两个顶点之间的距离为连接这两个顶点的简单路径上所包含的边的数量。

请计算所有距离为 $D$ 的顶点对 $(i,j)$ 的数量，并对 $998244353$ 取模后输出。

输入格式

输入从标准输入中给出，格式如下：

$N$ $D$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3 2

输出 #1

14

输入输出样例 #2

输入 #2

14142 17320

输出 #2

11284501

说明/提示

限制条件

• $2 \leq N \leq 10^6$
• $1 \leq D \leq 2\times 10^6$
• 输入的所有值均为整数

样例解释 1

给定的树结构如下图所示。

距离为 $2$ 的顶点对有 $(1,4),(1,5),(1,6),(1,7),(2,3),(3,2),(4,1),(4,5),(5,1),(5,4),(6,1),(6,7),(7,1),(7,6)$ 共 $14$ 对。

由 ChatGPT 4.1 翻译