[NOIP2006]2^k进制数

成绩 0 开启时间 2013年01月16日 星期三 12:00
折扣 0.8 折扣时间 2013年01月16日 星期三 12:00
允许迟交 关闭时间 2013年01月16日 星期三 12:00
输入文件 digital.in 输出文件 digital.out

【问题描述】

     设 r 是个 2k进制数,并满足以下条件:

( 1 ) r 至少是个 2 位的 2k进制数。
( 2 )作为 2k进制数,除最后一位外, r 的每一位严格小于它右边相邻的那一位。
( 3 )将 r 转换为 2 进制数 q 后,则 q 的总位数不超过 w 。

     在这里,正整数 k ( 1 ≤ k ≤ 9 )和 w ( w ≤ 4,000 )

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

     我们再从另一角度作些解释:设 S 是长度为 w 的 01 字符串(即字符串 S 由 w 个 “ 0 ” 或 “ 1 ” 组成), S 对应于上述条件( 3 )中的 q 。将 S 从右起划分为若干个长度为 k 的段,每段对应一位 2 k 进制的数,如果 S 至少可分成 2 段,则 S 所对应的二进制数又可以转换为上述的 2 k 进制数 r 。

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

     2 位数:高位为 1 : 6 个(即 12 , 13 , 14 , 15 , 16 , 17 ),高位为 2 : 5 个, … ,高位为 6 : 1 个(即 67 )。共 6+5+ … +1=21 个。

     3 位数:高位只能是 1 ,第 2 位为 2 : 5 个(即 123 , 124 , 125 , 126 , 127 ),第 2 位为 3 : 4 个, … ,第 2 位为 6 : 1 个(即 167 )。共 5+4+ … +1=15 个。

     所以,满足要求的 r 共有 36 个。

【输入文件】

     输入文件 digital.in 只有 1 行,为两个正整数,用一个空格隔开: k W

【输出文件】

    输出文件 digital.out 为 1 行,是一个正整数,为所求的计算结果,即满足条件的不同的 r 的个数(用十进制数表示),要求最高位不得为 0 ,各数字之间不得插入数字以外的其他字符(例如空格、换行符、逗号等)。

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

【输入输出样例】

digital.in

3 7

digital.out

36