Подсчитайте способы сделать число, образованное K конкатенациями числовой строки, делящимся на 5

Для заданной строки S , состоящей из N цифр и целого числа K , задача состоит в том, чтобы подсчитать количество способов удалить цифры из числа, образованного конкатенацией строки S , K раз, так что результирующая строка делится на 5 . Так как count может быть очень большим, выведите его по модулю 109 + 7.

Примеры:

Input: S = 1256, K = 1
Output: 4
Explanation:
Following are the ways to remove the characters so that the string S(= “1256”) is divisible by 5:

1. Remove the character 6 from the string S modifies the string to 125, which is divisible by 5.
2. Remove the character 1, and 6 from the string S modifies the string to 25, which is divisible by 5.
3. Remove the character 2, and 6 from the string S modifies the string to 15, which is divisible by 5.
4. Remove the character 1, 2, and 6 from the string S modifies the string to 5, which is divisible by 5.

Therefore, the total count of numbers formed which is divisible by 5 is 4.

Input: S = 13390, K = 2
Output: 528

Подход: Данную задачу можно решить тем, что число делится на 5 тогда и только тогда, когда его последняя цифра либо 0 , либо 5 . Если sol[i] — это количество способов сформировать числа, делящиеся на 5 , заканчивающиеся на i , то количество чисел определяется как (sol[1] + sol[2] + … + sol[N]) . Для каждого индекса i на справа от i можно удалить все цифры, а слева от i есть два варианта: либо удалить, либо взять, т. е. 2 ^{(i – 1)} .

Следовательно, общее количество чисел для K числа конкатенации определяется как:

ans = ans * (2^(K*N) -1) / (2^N – 1)

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N * log K)
Вспомогательное пространство: O(1)