Description

Let $r$ be a base $2^k$ number that satisfies the following conditions.

• $r$ has at least $2$ digits in base $2^k$.
• As a base $2^k$ number, except for the last digit, each digit of $r$ is strictly less than the digit immediately to its right.
• After converting $r$ to its binary representation $q$, the total number of bits of $q$ does not exceed $w$.

Here, the positive integers $k, w$ are given in advance.

Question: How many different $r$ satisfy the conditions above?

We further explain from another angle: Let $S$ be a length-$w$ $01$ string (i.e., $S$ consists of $w$ characters, each being $0$ or $1$), and $S$ corresponds to the $q$ mentioned in condition $3$. Partition $S$ from the right into blocks of length $k$, each block corresponding to one digit in base $2^k$. If $S$ can be partitioned into at least $2$ blocks, then the binary number represented by $S$ can be converted into the base $2^k$ number $r$ described above.

Example: Let $k=3, w=7$. Then $r$ is an octal number ($2^3=8$). Since $w=7$, a length-$7$ $01$ string, when split into blocks of $3$ bits, can be divided into $3$ blocks (namely $1, 3, 3$; the leftmost block has only one binary bit). The octal numbers that satisfy the conditions are:

$2$-digit numbers:
High digit is $1$: $6$ numbers (namely $12, 13, 14, 15, 16, 17$),
High digit is $2$: $5$ numbers,
...,
High digit is $6$: $1$ number (namely $67$).
In total, $6+5+…+1=21$ numbers.

$3$-digit numbers:
The high digit can only be $1$,
Second digit is $2$: $5$ numbers (namely $123, 124, 125, 126, 127$),
Second digit is $3$: $4$ numbers,
...,
Second digit is $6$: $1$ number (namely $167$).
In total, $5+4+…+1=15$ numbers.

Therefore, the total number of $r$ that satisfy the requirements is $36$.

Input Format

One line containing two positive integers $k, w$ separated by a space.

Output Format

Output one line with a single positive integer: the required result.
That is, the number of different $r$ that satisfy the conditions (in decimal). There must be no leading zeros, and no characters other than digits may be inserted between digits (such as spaces, line breaks, commas, etc.).

(Hint: The resulting positive integer may be large, but it will not exceed $200$ digits.)

3 7

36

Hint

Constraints
$1\le k \le 9$
$1\le w \le 3\times 10^4$

NOIP 2006 Senior Problem 4.

Translated by ChatGPT 5