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$

输出格式

输出答案。

3 2

14

14142 17320

11284501

提示

$2 \leq N \leq 10^6$ $1 \leq D \leq 2\times 10^6$ 输入中的所有值均为整数。下图描述了所给的树。 距离为 $2$ 的顶点对共有 $14$ 个：$(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)$。

标签: AtCoder|abc220E

来源

AtCoder|abc220E