如何计算具有某种属性的大A和B之间的整数？

在编程竞赛中，以下模式出现在很多任务中：

给定数字A和B是巨大的（可能是20个十进制数字或更多），确定具有特定属性P的A≤X≤B的整数X

SPOJ有很多类似的练习任务 。

有趣的属性的例子包括：

• “X的数字和是60”
• “X只包含数字4和7”
• “X是回文”，这意味着X的十进制表示等于其反向（例如，X = 1234321）

我知道，如果我们定义f（Y）是这样的整数X≤Y的数目，那么我们的问题的答案是f（B） – f（A – 1） 。 减less的问题是如何有效地计算函数f 。 在某些情况下，我们可以利用某些math属性来提出一个公式，但是这些属性往往比较复杂，我们没有足够的时间来进行比赛。

有没有更多的一般方法，在很多情况下工作？ 它也可以用来枚举具有给定属性的数字或计算它们的聚合吗？

其中的一个变化是find具有给定属性的第k个数字，当然这可以通过使用二分查找和计数function来解决。

Answer 1

事实上，这种模式有一个办法，经常工作。 它也可以用来枚举具有给定属性的所有X，只要它们的数目相当小。 你甚至可以使用它来聚合一些关联运算符在给定属性的所有X上，例如find它们的总和。

为了理解总体思路，让我们试着用X和Y的十进制表示forms来表示条件X≤Y。

假设我们有X = x ₁ x ₂ … x _{n – 1} x _n和Y = y ₁ y ₂ … y _{n – 1} y _n ，其中x _i和y _i是X和Y的十进制数字。如果数字有不同的长度，我们总是可以在较短的数字的前面加零数字。

让我们将leftmost_lo定义为x _i <y _i中最小的_i 。 如果没有这样的i，我们将leftmost_lo定义为n + 1 。 类似地，我们将leftmost_hi定义为x _i > y _i的最小_i ，否则定义n + 1 。

现在，X≤Y如果且恰好如果leftmost_lo <= leftmost_hi则为真。 有了这个观察，就可以对这个问题应用一种dynamic的编程方法，即将X的数字一个接一个地“设置”。 我将用你的例子来certificate这个问题：

计算X≤Y的整数X的数值f（Y），X的数位总和为60

令n为Y的位数， y[i]为上述定义的Y的第i个十进制数。 下面的recursionalgorithm解决了这个问题：

 count(i, sum_so_far, leftmost_lo, leftmost_hi): if i == n + 1: # base case of the recursion, we have recursed beyond the last digit # now we check whether the number X we built is a valid solution if sum_so_far == 60 and leftmost_lo <= leftmost_hi: return 1 else: return 0 result = 0 # we need to decide which digit to use for x[i] for d := 0 to 9 leftmost_lo' = leftmost_lo leftmost_hi' = leftmost_hi if d < y[i] and i < leftmost_lo': leftmost_lo' = i if d > y[i] and i < leftmost_hi': leftmost_hi' = i result += count(i + 1, sum_so_far + d, leftmost_lo', leftmost_hi') return result 

现在我们有f(Y) = count(1, 0, n + 1, n + 1) ，我们已经解决了这个问题。 我们可以添加记忆function，使其更快。 运行时对于这个特定的实现是O（n ⁴ ） 。 事实上，我们可以巧妙地优化这个想法，使其成为O（n） 。 这留给练习读者（提示：您可以将存储在sum_so_far > 60和sum_so_far > 60的信息压缩到一个位，并且如果sum_so_far > 60则可以修剪）。 解决scheme可以在这篇文章的结尾find。

如果仔细观察， sum_so_far这里仅仅是一个任意函数的例子，它从X的数字序列中计算一个值。它可以是任何可以逐位计算的函数，并且输出足够小的结果。 它可能是数字的产物，是一组数字的位掩码，满足一定的属性或许多其他的东西。

它也可能只是一个返回1或0的函数，具体取决于数字是否仅由数字4和7组成，这可以简单地解决第二个例子。 我们在这里必须要小心，因为我们允许在开始的时候有零，所以我们需要通过recursion函数调用一个额外的位，告诉我们是否仍然允许使用零作为数字。

计算X≤Y的整数X的数量f（Y），X是回文的

这一个稍微强硬。 我们需要小心前导零：回文数的镜像点取决于我们有多less前导零，所以我们需要跟踪前导零的数量。

有一个小技巧可以简化一下：如果我们可以用f（Y）来计算所有数字X必须与Y相同的数字数量，那么我们也可以通过迭代来解决原始问题所有可能的数字计数和加起来的结果。

所以我们可以假设我们根本没有领先零：

 count(i, leftmost_lo, leftmost_hi): if i == ceil(n/2) + 1: # we stop after we have placed one half of the number if leftmost_lo <= leftmost_hi: return 1 else: return 0 result = 0 start = (i == 1) ? 1 : 0 # no leading zero, remember? for d := start to 9 leftmost_lo' = leftmost_lo leftmost_hi' = leftmost_hi # digit n - i + 1 is the mirrored place of index i, so we place both at # the same time here if d < y[i] and i < leftmost_lo': leftmost_lo' = i if d < y[n-i+1] and n-i+1 < leftmost_lo': leftmost_lo' = n-i+1 if d > y[i] and i < leftmost_hi': leftmost_hi' = i if d > y[n-i+1] and n-i+1 < leftmost_hi': leftmost_hi' = n-i+1 result += count(i + 1, leftmost_lo', leftmost_hi') return result 

结果将再次是f(Y) = count(1, n + 1, n + 1) 。

更新：如果我们不仅要计算数字，而且可能枚举它们或者计算一些不暴露组结构的聚合函数，我们还需要在recursion过程中强制执行X的下界。 这增加了一些参数。

更新2： O（n）“数字总和60”示例的解决scheme：

在这个应用程序中，我们把数字从左到右。 既然我们只关心是否leftmost_lo < leftmost_hi成立，让我们添加一个新的参数lo 。 lo是真正的iif leftmost_lo leftmost_lo < i ，否则为false。 如果lo是真的，我们可以使用位置i任何数字。 如果它是错误的，我们只能使用数字0到Y [i]，因为任何更大的数字都会导致leftmost_hi = i < leftmost_lo ，因此不会导致解决scheme。 码：

 def f(i, sum_so_far, lo): if i == n + 1: return sum_so_far == 60 if sum_so_far > 60: return 0 res = 0 for d := 0 to (lo ? 9 : y[i]): res += f(i + 1, sum + d, lo || d < y[i]) return res 

可以说，这种看待它的方式比起leftmost_lo / leftmost_hi方法稍微简单一些，但也不那么明确。 它也不能马上处理像回文问题那样的复杂情况（尽pipe它也可以在那里使用）。