浅谈数位类统计问题

浅谈数位类统计问题,山东省青岛第二中学 刘聪,引入,在信息学竞赛中，有一类与数位有关的区间统计问题。 例如： 求[1,n]中所有数的各位数字之和。 求[1,n]中各位数字之和为定值的数的个数。 将[m,n]中的数字分组，每组包含连续的一段数，且数字之和不能超过定值，求分组数。 …… 如何求解？,n≤1018!,【例题1】Amount of degrees,求给定区间[X,Y]中满足下列条件的整数个数：这个数恰好等于K个互不相等的B的整数次幂之和。 例如，设X=15，Y=20，K=2，B=2，则有且仅有下列三个数满足题意： 17 = 24+20， 18 = 24+21， 20 = 24+22。 数据规模：1 ≤ X ≤ Y ≤ 231−1，1 ≤ K ≤ 20， 2 ≤ B ≤ 10。,【例题1】Amount of degrees,由于所求的幂互不相等，符合条件的数写成B进制一定只由0和1组成。 因此我们只考虑B=2的情况。 此处区间满足区间减法，即count(X,Y)=count(0,Y)-count(0,X-1) 因此我们唯一需要求的就是，给定n，求出所有不超过n的正整数中，其二进制表示恰好含有K个“1“的有多少。,【例题1】Amount of degrees,这里，我使用一棵完全二叉树来代表一个区间内的数。 例如右图中高度为4 的完全二叉树就可以 代表所有长度为4 的二进制数。 其范围为[0,24-1] 每个叶子就代表了 一个数。,【例题1】Amount of degrees,假设K=3 ，n=13，其二进制为1101。 我们从根“走“到n所在的叶子 每次“向右走”时， 左侧的子树都是 完整的完全二叉 树，且所有小于 n的整数都包含在其中。,【例题1】Amount of degrees,因此，我们实际上只需对 这三棵子树进行 统计。 当然，不能忘记n本身。,这棵树中有多少数含3个1？,这棵树中有多少数含2个1？ （因为祖先已有1个1）,这棵树中有多少数含1个1？,【例题1】Amount of degrees,很容易递推求出这个问题： 设f[h,s]表示在高度为h的完全二叉树包含的数中（范围是[0,2h-1]），二进制中恰含s个1的数有多少。 f[h,s]=f[h-1,s]+f[h-1,s-1],左子树中的个数,右子树中的个数,【例题1】Amount of degrees,剩下的问题就是，如何将任意进制问题转化为二进制问题。 只需贪心将n的B进制表示转化为只含01：找到n的左起第一位大于1的数位，将它以及它右边所有数位赋为1。 递推求f的时间复杂度为O(log2(n))，每次询问的时间复杂度为O(log(n))，因此总时间复杂度为O(log2(n))。 问题得到完美解决！,【例题1】Amount of degrees,实际上，我们也可以只用“位”的思想来考虑这个问题，而不使用树的思想。 我们每次找到n的“1“数位，将它赋为0，则其右面的数位可任取0、1。 可根据组合数算出满足题意的数的个数。 穷举所有“1”数位，计算组合数，即可完成询问。 事实上，f的递推公式正是组合数公式！ 与树的思想异曲同工!,f[h,s]=f[h-1,s]+f[h-1,s-1],C[n,k]=C[n-1,k]+C[n-1,k-1],【例题1】Amount of degrees,使用高度为h的完全B叉树表示所有长度为h的B进制数，思考起来更加直观，在处理较复杂问题时优点明显。 当然，最终程序我们并不真正建树，它的作用只是帮助我们思考。 无论从树结构考虑还是从数位的角度考虑，基本思想都是：,逐位确定,【例题4】Tickets,有一位售票员给乘客售票。对于每位乘客，他会卖出多张连续的票，直到已卖出的票的编号的数位之和不小于给定的正数K。然后他会按照相同的规则给下一位乘客售票。 初始时，售票员持有的票的编号是从L到R的连续整数。请你求出，售票员可以售票给多少位乘客。 数据规模：1 ≤ L ≤ R ≤ 1018，1 ≤ K ≤ 1000。,【例题4】Tickets,有了例1的基础，本题基本思路也是从特殊到一般： 能否将原问题的区间拆分为一些长度为10k的子区间，再合并得到原区间的答案？ 亦即，将原树拆分为若干完整的完全十叉数，根据子树的信息合并得到原问题的答案。 一个比较棘手的问题是，这棵树的前几个元素可能会并入之前的小组，而不是作为一个新的小组。 换言之，只使用树的高度无法表示一组状态。,添加状态！,【例题4】Tickets,设f[h,sum,rem]表示对于高度为h的完全十叉树，其每个数的数位之和需要额外添加sum，在这棵树之前的最后一个小组剩余空间为rem，所能得到的小组情况。 f返回值有两个：f[h,sum,rem].a记录这棵树被划分成的小组数量，f[h,sum,rem].b记录这些小组中的最后一组的剩余空间，以便与下一组合并。 同例1一样，这里f的值也由其10棵子树合并而成： for i:=0 to 9 do f[h,sum,rem]:= merge( f[h,sum,rem] , f[h-1,sum+i,f[h,sum,rem].b]); 也就是之前得到的“b“值作为下一棵子树的“rem“值。,function merge(x,y); x.a:=x.a+y.a; x.b:=y.b; return x;,