string - 求一个 n 位数字中能被 8 整除的子序列的个数

Question

给定 n = 1 到 10^5，以十进制格式存储为字符串。

示例:如果 n = 968，则在所有子序列(9、6、8、96、68、98、968)中，有 3 个子序列(即 968、96 和 8)可被 8 整除.所以，答案是3。

由于答案可能非常大，因此打印答案模 (10^9 + 7)。

Answer 1

您可以使用动态规划。令 f(len, sum) 为长度为 len 的前缀的子序列数，其总和为 sum 模 8 ( >sum 范围从 0 到 7)。

对于 len = 1，f 的值是显而易见的。转换过程如下:

1. 我们可以在新位置开始一个新的子序列:f(len, a[i] % 8) += 1。

2. 我们可以从较短的前缀继续任何子序列:

   for old_sum = 0..7
        f(len, (old_sum * 10 + a[i]) % 8) += f(len - 1, old_sum) // take the new element
        f(len, old_sum) += f(len - 1, old_sum) // ignore the new element
   

当然，您可以执行所有计算模块 10^9 + 7 并使用标准整数类型。

答案是 f(n, 0)(考虑所有元素，模 8 的总和为 0)。

此解决方案的时间复杂度为 O(n)(因为有 O(n) 状态，并且每个状态有 2 个转换)。

注意:如果数字不能有前导零，则可以为状态添加一个参数:一个标志，指示子序列的第一个元素是否为零(该序列不应扩展)。解决方案的其余部分保持不变。