E - Complete Binary Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 450 点

問題文

1 から N までの番号が付けられた N 頂点からなる木があります。 各 i\ (2 \leq i \leq N) について、頂点 i と頂点 \lfloor \frac{i}{2} \rfloor を結ぶ辺が張られています。 逆に、これら以外の辺は存在しません。

この木において、頂点 X との距離が K である頂点の数を求めてください。 ただし、2 頂点 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 である頂点は 2 の 1 つです。
  • 頂点 2 との距離が 1 である頂点は 1,4,5 の 3 つです。
  • 頂点 2 との距離が 2 である頂点は 3,8,9,10 の 4 つです。
  • 頂点 2 との距離が 3 である頂点は 6,7 の 2 つです。
  • 頂点 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

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