浅谈数位类统计问题
浅谈数位类统计问题,山东省青岛第二中学 刘聪,引入,在信息学竞赛中,有一类与数位有关的区间统计问题。 例如: 求[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;,