No.916 Encounter On A Tree
タグ : / 解いたユーザー数 112
作問者 :
tempura_pp
Problem Statement
You are given a perfect binary tree of depth $d$.
Here, a perfect binary tree is a tree in which every vertex either "is a leaf" or "has two children", and in which all leaves have the same depth.
The depth of the root is $1$, and the depth of the leaves is $d$.
Furthermore, for the vertex that has depth $i$ and is the $j$-th from the left, its position is defined as $2^{i-1}+j-1$,
and the vertex at position $x$ is called vertex $x$.
Consider writing distinct numbers from $1$ to $2^d-1$, one each, on the $2^d-1$ vertices of this tree.
The following conditions must be satisfied.
- For all $i,\ j$, if the depth of vertex $i$ is greater than the depth of vertex $j$, then the number written on vertex $i$ is greater than the number written on vertex $j$.
- The number of edges on the path connecting the vertex on which $l$ is written and the vertex on which $r$ is written is $k$.
Here, two ways of writing the numbers are considered different if there exists a vertex $i$ such that the numbers written on vertex $i$ differ.
Input
$d\ l\ r\ k$
All inputs are integers.
$2 \le d \le 20$
$1 \le l < r \le 2^d-1$
$1 \le k \le 10^5$
Output
Output the answer on one line. Print a newline at the end.
Sample
Sample 1
Input
2 1 2 1
Output
2
There are 2 ways: (vertex 1, vertex 2, vertex 3)=(1,2,3), (1,3,2).
Sample 2
Input
2 2 3 2
Output
2
Sample 3
Input
3 4 5 4
Output
32
Sample 4
Input
4 3 6 2
Output
0
Sample 5
Input
17 34 45 4
Output
8695321
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。