Problem 1000 --2^k进制数

1000: 2^k进制数

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $407$ 正确数量 $80$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签
设$r$是个$2^k$ 进制数,并满足以下条件: (1)$r$至少是个2位的$2^k$ 进制数。 (2)作为$2^k$ 进制数,除最后一位外,r的每一位严格小于它右边相邻的那一位。 (3)将r转换为二进制数$q$后,则$q$的总位数不超过$w$。 在这里,正整数$k (1\le k \le9)$和$w$ $(k\lt w \le 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个。

只有1行,为两个正整数,用一个空格隔开: $k$和$w$

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

3  7
36

推荐代码 查看1000 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$0 $ms] 大喵-sama 899679 2022-10-09 21:53:31
内存最少[$1308 $KB] 敢敢的心心 812815 2022-03-01 08:29:35
第一AC AOJ大管家 2959 2016-05-18 22:57:18
第一挑战 AOJ大管家 2099 2016-05-16 16:48:35

赛题来源/所属竞赛 NA N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛