#P6875. a
a
题目描述
对于一个非负整数 ,一次操作可以将它减去 ,或选择一个非负整数 ,在 的第 个二进制位为 时减去 。第 位是最低位。
记 为将 变成 所需的最少操作次数。给定 ,求下式对 取模的结果。
输入格式
一行一个合法的二进制串,表示 。输入没有前导零。
输出格式
一行一个整数,表示答案对 取模后的结果。
样例
111
43
数据范围
- 对于 的数据, 的二进制表示不超过 位。
- 对于 的数据, 的二进制表示不超过 位。
- 对于所有数据, 的二进制表示不超过 位。
对于一个非负整数 x,一次操作可以将它减去 1,或选择一个非负整数 i,在 x 的第 i 个二进制位为 1 时减去 2i。第 0 位是最低位。
记 f(x,y) 为将 x 变成 y 所需的最少操作次数。给定 N,求下式对 1000000007 取模的结果。
x=0∑Ny=0∑xf(x,y)一行一个合法的二进制串,表示 N。输入没有前导零。
一行一个整数,表示答案对 1000000007 取模后的结果。
111
43