Вопрос:

Сумма f (x) в диапазоне

algorithm dynamic-programming digits

13 просмотра

1 ответ

1 Репутация автора

Даны два числа L и R. Они могут иметь до 10 ^ 5 цифр. Функция f (x) определяется следующим образом:

рассмотрим х хранится в строке s и х = 21999301

для каждого s [i] = s [i-1] положим s [i] = 0

поэтому здесь значение f (x) будет 21900301

Учитывая L и R, мы должны найти сумму f (x) для всех x между L и R (включительно) по модулю (10 ^ 9 + 7).

например, если L = 8 и R = 12,

ответ будет (8 + 9 + 10 + 10 + 12) (по модулю 10 ^ 9 + 7) = 49 (потому что f (11) = 10)

Поскольку цифры могут иметь до 10 ^ 5 цифр. Я не могу даже думать о грубой силе, иначе мое решение истечет.

Затем я подумал об использовании цифрового динамического программирования с использованием этого подхода:

Сохраните dp [x] как сумму f (x) всех чисел x

Предположим, что L имеет 10 цифр, а R имеет 11 цифр, поэтому мой ответ выглядит следующим образом

(dp [10] + сумма f (x) для 11-значных чисел, меньших, чем R) - (dp [9] + сумма f (x) для 10-значных чисел, меньших L)

Я думал об этом, но я не могу кодировать динамическое программирование.

Кто-нибудь может помочь?

Автор: Samay Bhardwaj Источник Размещён: 11.08.2019 06:34

Ответы (1)


0 плюса

79 Репутация автора

Вы можете найти среднее значение между двумя числами, а затем просто умножить.

В вашем примере среднее значение равно 10.

9 + 11 = 10 + 10
8 + 12 = 10 + 10

Ваш алгоритм, если медиана является четным значением, будет (max - min) * median(медиана является целым числом).

с нечетным расстоянием это не работает, потому что медиана не является целым числом, но вы можете просто убрать номер хвоста, чтобы добавить его позже.

Автор: Claudio Размещён: 11.08.2019 06:58
Вопросы из категории :
32x32