幸运数字八 - Hackerrank-W28

Question

给定一个n位正整数，计算并打印通过连接给定数字的可被8整除的数字形成的子序列的数量。由于结果可能很大，打印结果模（10** 9 + 7). 问题可以阅读here

看起来很简单，我试着解决了。我的方法是尝试跟踪所有可被 8 整除的 3 位、2 位和 1 位数字。因为任何最后 3 位数字可被 8 整除的数字都可以被 8 整除，我厌倦了为 3 位数字保留一棵树并跟踪出现的次数（2**p，p=前面字符的数量给出了序列的数量），但这是不对的，因为我无法处理一些数字交错的情况（例如 9868）。

比赛结束后，由于社论不够清晰，我一直在寻找优雅的解决方案。我遇到了一个，但无法理解发生了什么。有人可以解释以下解决方案背后的数学原理吗？

#!/bin/python3
import sys

# n = int(input().strip())
# number = input().strip()

n = 10
# number = "0123456789" #81
number = "1234567890" #109

# n = 5
# number = "9868" #5

mods = [0, 0, 0, 0, 0, 0, 0, 0]
P = 10**9 + 7
for k in number:
   m = int(k) % 8
   new_mods = mods[:]
   new_mods[m] += 1
   for i in range(8):
      new_index = (i*10+m)%8
      new_mods[new_index] = (new_mods[new_index] + mods[i]) % P
   mods = new_mods

print(mods[0])

ideone link

Answer 1

该算法背后的想法是增量处理给定数字的前缀，并针对每个前缀和从 0 到 7 的每个 r 计算该数字的子序列数构成等于 r 模 8.

的数字的前缀

设[n₀n₁...nₓ]为输入数字。

令 S(i, r) 为前缀 [n₀n₁...nᵢ] 的子序列数，这些子序列构成一个等于 r 模 8.

的数

为了计算 0 ≤ r ≤ 7 的 S(i+1, r)，我们只需要知道 0 ≤ r ≤ 7 的 S(i, r)。这就是可以在线性时间内一个一个地处理数字的原因。

[n₀n₁...nᵢ₊₁]有3种子序列：

不包含 nᵢ₊₁ 的子序列。
- [n₀n₁...nᵢ] 的每个子序列 [a...b] 都有 [n₀n₁...nᵢ₊₁] 的相等子序列。
- 对于从 0 到 7 的每个 r，我们将 S(i, r) 添加到 S(i+1, r)，从而将它们考虑在内。
包含 nᵢ₊₁ 且前面至少有一个数字的子序列。
- 对于 [n₀n₁...nᵢ] 的每个等于 r 模 8 的子序列 [a...b]，[n₀n₁...nᵢ₊₁] 的子序列 [a...bnᵢ₊₁] 是等于 (r*10+nᵢ₊₁)%8 模 8（因为 [a...bnᵢ₊₁] = 10*[a...b] + nᵢ₊₁）。
- 对于从 0 到 7 的每个 r，我们将 S(i, r) 添加到 S(i+1, (r*10+nᵢ₊₁)%8)，从而将它们考虑在内。
One-digit 子序列 [nᵢ₊₁]。
- 我们通过将 1 添加到 S(i+1, nᵢ₊₁ % 8) 来考虑它。

在您引用的代码中：

S(i, 0), ..., S(i, 7) 是 mods — 前一个前缀的 8 个数字的数组。
S(i+1, 0), ..., S(i+1, 7) 是 new_mods — 当前前缀的 8 个数字数组。
nᵢ₊₁ 是 k — 当前前缀的最后一位。

幸运数字八 - Hackerrank-W28

Lucky Number Eight - Hackerrank-W28

python

algorithm

puzzle