103214: [Atcoder]ABC321 E - Complete Binary Tree

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:8 Solved:0

Description

Score : $450$ points

Problem Statement

There is a tree with $N$ vertices numbered $1$ to $N$. For each $i\ (2 \leq i \leq N)$, there is an edge connecting vertex $i$ and vertex $\lfloor \frac{i}{2} \rfloor$. There are no other edges.

In this tree, find the number of vertices whose distance from vertex $X$ is $K$. Here, the distance between two vertices $u$ and $v$ is defined as the number of edges in the simple path connecting vertices $u$ and $v$.

You have $T$ test cases to solve.

Constraints

  • $1\leq T \leq 10^5$
  • $1\leq N \leq 10^{18}$
  • $1\leq X \leq N$
  • $0\leq K \leq N-1$
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where $\mathrm{test}_i$ represents the $i$-th test case:

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

Each test case is given in the following format:

$N$ $X$ $K$ 

Output

Print $T$ lines.

The $i$-th line $(1 \leq i \leq T)$ should contain the answer to the $i$-th test case as an integer.


Sample Input 1

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

Sample Output 1

1
3
4
2
0

The tree for $N=10$ is shown in the following figure.

Here,

  • There is $1$ vertex, $2$, whose distance from vertex $2$ is $0$.
  • There are $3$ vertices, $1,4,5$, whose distance from vertex $2$ is $1$.
  • There are $4$ vertices, $3,8,9,10$, whose distance from vertex $2$ is $2$.
  • There are $2$ vertices, $6,7$, whose distance from vertex $2$ is $3$.
  • There are no vertices whose distance from vertex $2$ is $4$.

Sample Input 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

Sample Output 2

1556480
140703128616960
8
17732923532771328
65536
24576
2147483640
33776997205278720
7881299347898368
27021597764222976

Output

分数:450分

问题描述

有一个有N个顶点的树,编号为1到N。 对于每个$i\ (2 \leq i \leq N)$,存在一条连接顶点i和顶点$\lfloor \frac{i}{2} \rfloor$的边。 没有其他边。

在这个树中,找出与顶点X的距离为K的顶点的数量。 这里,两个顶点$u$和$v$之间的距离定义为连接顶点$u$和$v$的简单路径上的边的数量。

你需要解决T个测试用例。

约束

  • $1\leq T \leq 10^5$
  • $1\leq N \leq 10^{18}$
  • $1\leq X \leq N$
  • $0\leq K \leq N-1$
  • 所有输入值都是整数。

输入

输入从标准输入给出以下格式,其中$\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个测试用例的答案,即整数。


样例输入1

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

样例输出1

1
3
4
2
0

当N=10时,树如下图所示。

在这里,

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

样例输入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

HINT

对于一棵完全二叉树,求与点x距离为k的点的数量?

加入题单

上一题 下一题 算法标签: