Score : $500$ points

问题描述

我们有一棵包含 $2^N-1$ 个顶点的树。
这些顶点按顺序编号为 $1$ 至 $2^N-1$。对于每个 $1\leq i < 2^{N-1}$，存在以下边：

• 一条无向边连接顶点 $i$ 和顶点 $2i$，
• 一条无向边连接顶点 $i$ 和顶点 $2i+1$。

除此之外没有其他边。

设两个顶点之间的距离是连接这两个顶点的简单路径上的边数。

求满足顶点对 $(i, j)$ 之间距离为 $D$ 的数量模 $998244353$ 后的结果。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have a tree with $2^N-1$ vertices.
The vertices are numbered $1$ through $2^N-1$. For each $1\leq i < 2^{N-1}$, the following edges exist:

• an undirected edge connecting Vertex $i$ and Vertex $2i$,
• an undirected edge connecting Vertex $i$ and Vertex $2i+1$.

There is no other edge.

Let the distance between two vertices be the number of edges in the simple path connecting those two vertices.

Find the number, modulo $998244353$, of pairs of vertices $(i, j)$ such that the distance between them is $D$.

Constraints

• $2 \leq N \leq 10^6$
• $1 \leq D \leq 2\times 10^6$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $D$

Output

Print the answer.

Sample Input 1

3 2

Sample Output 1

14

The following figure describes the given tree.

There are $14$ pairs of vertices such that the distance between them is $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)$.

Sample Input 2

14142 17320

Sample Output 2

11284501

update @ 2024/3/10 09:43:47