#P6875. a

    ID: 6706 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-数位 DP位计数滚动数组

a

题目描述

对于一个非负整数 xx,一次操作可以将它减去 11,或选择一个非负整数 ii,在 xx 的第 ii 个二进制位为 11 时减去 2i2^i。第 00 位是最低位。

记 f(x,y)f(x,y) 为将 xx 变成 yy 所需的最少操作次数。给定 NN,求下式对 10000000071000000007 取模的结果。

∑x=0N∑y=0xf(x,y)\sum_{x=0}^{N}\sum_{y=0}^{x} f(x,y)

输入格式

一行一个合法的二进制串,表示 NN。输入没有前导零。

输出格式

一行一个整数,表示答案对 10000000071000000007 取模后的结果。

样例

111
43

数据范围

  • 对于 20%20\% 的数据,NN 的二进制表示不超过 1010 位。
  • 对于 50%50\% 的数据,NN 的二进制表示不超过 2020 位。
  • 对于所有数据,NN 的二进制表示不超过 500500 位。

原 PDF 题面