102204: [AtCoder]ABC220 E - Distance on Large Perfect Binary Tree
Description
Score : $500$ points
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
Input
题意翻译
给定一个完全二叉树，一共有 $2 ^ N - 1$ 个节点，按 $1$ 到 $2 ^ N - 1$ 编号。其中，对于 $1 \le i < 2 ^ {N - 1}$，有： + 节点 $i$ 与节点 $2i$ 有一条无向边。 + 节点 $i$ 与节点 $2i + 1$ 有一条无向边。 $2$ 节点之间的距离是连接该 $2$ 节点的简单路径中包含的边数。 求有多少组节点 $(i,j)$，满足节点 $i$ 与节点 $j$ 的距离为 $D$。 答案模 $998244353$。Output
问题描述
我们有一个具有$2^N-1$个顶点的树。
顶点编号为$1$到$2^N-1$。对于每个$1\leq i < 2^{N-1}$，存在以下边：
- 连接顶点$i$和顶点$2i$的无向边，
- 连接顶点$i$和顶点$2i+1$的无向边。
没有其他边。
设两个顶点之间的距离为连接这两个顶点的简单路径中的边的数量。
找到距离为$D$的顶点对$(i, j)$的数量，模$998244353$。
约束
- $2 \leq N \leq 10^6$
- $1 \leq D \leq 2\times 10^6$
- 输入中的所有值都是整数。
输入
从标准输入按以下格式给出输入：
$N$ $D$
输出
打印答案。
样例输入1
3 2
样例输出1
14
以下图形描述了给定的树。
有$14$对顶点，它们之间的距离为$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)$。
样例输入2
14142 17320
样例输出2
11284501