Given an n-digit positive integer, count and print the number of sub-sequences formed by concatenating the given number's digits that are divisible by 8. As the result can be large, print the result modulo (10**9 + 7). the question can be read here
Looks simple and i tried to solve it. My approach, tried to keep track of all 3 digit, 2 digit and 1 digit numbers divisible by 8. since any number with last 3 digits divisible by 8 is exactly divisible by 8, i tired to keep a tree for 3 digit and track occurrences (2**p, p=number of preceding characters gives number of sequences), but this was not right since i could not handle some scenarios where digits are interleaved (example 9868).
After the contest is over, i was looking for elegant solution since the Editorial was not clear enough. I came across one, but could not understand whats going on. Could someone explain the math behind the following solution ?
#!/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])
The idea behind the algorithm is to incrementally process prefixes of the given number and for every prefix and every r from 0 to 7 to calculate the number of subsequences of that prefix that form a number equal to r modulo 8.
Let [n₀n₁...nₓ] be the input number.
Let S(i, r) be the number of subsequences of the prefix [n₀n₁...nᵢ] that form a number equal to r modulo 8.
In order to calculate S(i+1, r) for 0 ≤ r ≤ 7 we only need to know S(i, r) for 0 ≤ r ≤ 7. That's what makes it possible to process the digits one by one in linear time.
There are 3 kinds of subsequences of [n₀n₁...nᵢ₊₁]:
nᵢ₊₁.
[a...b] of [n₀n₁...nᵢ] there is an equal subsequence of [n₀n₁...nᵢ₊₁]. S(i, r) to S(i+1, r) for every r from 0 to 7.nᵢ₊₁ and at least one digit before it.
[a...b] of [n₀n₁...nᵢ] that is equal to r modulo 8 there is a subsequence [a...bnᵢ₊₁] of [n₀n₁...nᵢ₊₁] that is equal to (r*10+nᵢ₊₁)%8 modulo 8 (since [a...bnᵢ₊₁] = 10*[a...b] + nᵢ₊₁). S(i, r) to S(i+1, (r*10+nᵢ₊₁)%8) for every r from 0 to 7.[nᵢ₊₁].
1 to S(i+1, nᵢ₊₁ % 8).In the code you quoted:
S(i, 0), ..., S(i, 7) is mods — the array of 8 numbers for the previous prefix.S(i+1, 0), ..., S(i+1, 7) is new_mods — the array of 8 numbers for the current prefix.nᵢ₊₁ is k — the last digit of the current prefix.