#66. [NOIP2006 提高组] 2^k进制数

[NOIP2006 提高组] 2^k进制数

题目描述

rr 是个 2k2^k 进制数,并满足以下条件:

  • rr 至少是个 22 位的 2k2^k 进制数。
  • 作为 2k2^k 进制数,除最后一位外,rr 的每一位严格小于它右边相邻的那一位。
  • rr 转换为二进制数 qq 后,则 qq 的总位数不超过 ww

在这里,正整数 k,wk,w 是事先给定的。

问:满足上述条件的不同的 rr 共有多少个?

我们再从另一角度作些解释:设 SS 是长度为 ww0101 字符串(即字符串 SSww0011 组成),SS 对应于上述条件三中的 qq。将 SS 从右起划分为若干个长度为 kk 的段,每段对应一位 2k2^k 进制的数,如果 SS 至少可分成 22 段,则 SS 所对应的二进制数又可以转换为上述的 2k2^k 进制数 rr

例:设 k=3,w=7k=3,w=7。则 rr 是个八进制数( 23=82^3=8 )。由于 w=7w=7,长度为 770101 字符串按 33 位一段分,可分为 33 段(即 1,3,31,3,3,左边第一段只有一个二进制位),则满足条件的八进制数有:

22 位数: 高位为 1166 个(即 12,13,14,15,16,1712,13,14,15,16,17 ), 高位为 2255 个, …, 高位为 6611 个(即 6767 )。 共 6+5++1=216+5+…+1=21 个。

33 位数: 高位只能是 11, 第 22 位为 2255 个(即 123,124,125,126,127123,124,125,126,127 ), 第 22 位为 3344 个, …, 第 22 位为 6611 个(即 167167 )。 共 5+4++1=155+4+…+1=15 个。

所以,满足要求的 rr 共有 3636 个。

输入格式

一行两个正整数 k,wk,w 用一个空格隔开:

输出格式

一行一个个正整数,为所求的计算结果。 即满足条件的不同的 rr 的个数(用十进制数表示),要求不得有前导零,各数字之间不得插入数字以外的其他字符(例如空格、换行符、逗号等)。

(提示:作为结果的正整数可能很大,但不会超过 200200 位)

样例

3 7
36

提示

【数据范围】 1k91\le k \le 9 1w3×1041\le w \le 3\times 10^4