AT_abc321_e [ABC321E] Complete Binary Tree

题目描述

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。对于每个 $i\ (2\leq i\leq N)$，都存在一条连接顶点 $i$ 和顶点 $\lfloor \frac{i}{2} \rfloor$ 的边。除此之外，不存在其他边。

在这棵树中，请你求出与顶点 $X$ 的距离恰好为 $K$ 的顶点个数。这里，两个顶点 $u,v$ 之间的距离被定义为连接 $u$ 和 $v$ 的简单路径上包含的边的数量。

给定 $T$ 组测试数据，请分别输出每组的答案。

输入格式

输入按以下格式从标准输入读入。这里，$\mathrm{test}_i$ 表示第 $i$ 个测试用例。

$T$
$\mathrm{test}_1$
$\mathrm{test}_2$
$\vdots$
$\mathrm{test}_T$

每组测试数据格式如下：

$N\ X\ K$

输出格式

输出 $T$ 行。

第 $i$ 行输出第 $i$ 个测试用例的答案，结果为一个整数。

输入输出样例 #1

输入 #1

5
10 2 0
10 2 1
10 2 2
10 2 3
10 2 4

输出 #1

1
3
4
2
0

输入输出样例 #2

输入 #2

10
822981260158260522 52 20
760713016476190629 2314654 57
1312150450968417 1132551176249851 7
1000000000000000000 1083770654 79
234122432773361868 170290518806790 23
536187734191890310 61862 14
594688604155374934 53288633578 39
1000000000000000000 120160810 78
89013034180999835 14853481725739 94
463213054346948152 825589 73

输出 #2

1556480
140703128616960
8
17732923532771328
65536
24576
2147483640
33776997205278720
7881299347898368
27021597764222976

说明/提示

限制条件

• $1\leq T\leq 10^5$
• $1\leq N\leq 10^{18}$
• $1\leq X\leq N$
• $0\leq K\leq N-1$
• 输入均为整数

样例解释 1

当 $N=10$ 时，这棵树的结构如下图所示。

此时：

• 与顶点 $2$ 距离为 $0$ 的顶点只有 $2$ 这一个，共 $1$ 个。
• 与顶点 $2$ 距离为 $1$ 的顶点有 $1,4,5$，共 $3$ 个。
• 与顶点 $2$ 距离为 $2$ 的顶点有 $3,8,9,10$，共 $4$ 个。
• 与顶点 $2$ 距离为 $3$ 的顶点有 $6,7$，共 $2$ 个。
• 与顶点 $2$ 距离为 $4$ 的顶点不存在。

由 ChatGPT 4.1 翻译