Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5172 --数字转换
5172: 数字转换
警告!
题目
状态
题解
题目描述
对于任意十进制正整数$x$,我们定义一次数字转换是将数字$x$转变为$x$在二进制表示下$1$的个数。显然,任意正整数经过若干次数字转换后,最终都会得到$1$,此时经过的转换次数我们也称之为**最大转换次数**。 例如$(27)_{10}$在二进制下为$(11011)_2$,则$27$经过一次数字转换后,得到了$4$,$4$再经过一次数字转换后得到了$1$。所以$27$经过$2$次转换后,得到了$1$,即$27$的最大转换次数为$2$。 现给定$x$与$k$,请计算出$1$~$x$中,有多少数字的最大转换次数为$k$。
输入
输入第一行,一个二进制表示的正整数$x$ 输入第二行,一个非负整数$k$
输出
输出$1$~$x$中,最大转换次数为$k$的数字个数,并对$10^9+7$取模。
样例输入输出
输入#1
复制
11 1
输出#1
复制
1
输入#2
复制
11011 2
输出#2
复制
13
提示
+ 对 $30\%$ 的数据,$1\leq x \leq 2^{20}$, $0\leq k\leq 5$ + 对 $50\%$ 的数据,$1\leq x \leq 2^{63}-1$, $0\leq k\leq 20$ + 对 $100\%$ 的数据,$1\leq x \leq 2^{1000}$, $0\leq k\leq 10^3$。 样例1说明:1~3中,只有2的最大转换次数为1
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
提高+/省选-
标签
数学与数论
点击显示
if ($pr_flag) { ?>
递交数
1
已通过
1
} ;?>
通过率
100%
时间限制
1 秒
内存限制
256 MB
来源
YACS2020年9月月赛甲组
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和