P1066 2^k进制数

    • 1.4K通过
    • 3.8K提交
  • 题目提供者 CCF_NOI
  • 评测方式 云端评测
  • 标签 数论,数学 进制 高精 NOIp提高组 2006
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    (1)r至少是个$2$位的$2^k$ 进制数。

    (2)作为$2^k$ 进制数,除最后一位外,$r$的每一位严格小于它右边相邻的那一位。

    (3)将$r$转换为$2$进制数$q$后,则$q$的总位数不超过$w$。

    在这里,正整数$k(1≤k≤9)$和$w(k<W≤30000)$是事先给定的。

    问:满足上述条件的不同的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$个。

    输入输出格式

    输入格式:

    $2$个正整数,用一个空格隔开:

    $k W$

    输出格式:

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

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

    输入输出样例

    输入样例#1: 复制
    3 7
    输出样例#1: 复制
    36

    说明

    NOIP 2006 提高组 第四题

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。