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$ 行 $(1 \leq i \leq T)$ 应该包含第 $i$ 个测试用例的答案，作为整数。

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

1
3
4
2
0

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

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$ 所有输入值均为整数。当 $N=10$ 时的树如图所示。 在这里，

有 $1$ 个顶点，$2$，与顶点 $2$ 的距离为 $0$。 有 $3$ 个顶点，$1,4,5$，与顶点 $2$ 的距离为 $1$。 有 $4$ 个顶点，$3,8,9,10$，与顶点 $2$ 的距离为 $2$。 有 $2$ 个顶点，$6,7$，与顶点 $2$ 的距离为 $3$。 没有顶点与顶点 $2$ 的距离为 $4$。

标签: AtCoder|abc321E

来源

AtCoder|abc321E