Задача G ШАД 2025

Приветствую всех, на повестке дня разберем легчайшую первую задачку из алгоритмической части второго этапа отбора в ШАД. Математическая часть выдалась трудной, поэтому выигрышной стратегией было забирать бесплатные баллы за задачки G и H.

Условие задачи G
На вход дана число A (1 <= len(A) <= 10^6, где len(A) это количество цифр в числе). Пусть S(A) - сумма всех циклических сдвигов, числа A, от вас требуется посчитать сумму всех цифр A.

Разбор
Посмотрим, как работают циклический сдвиги и как изменяются позиции i-го элемента:
нулевой сдвиг: a[i]
первый сдвиг: a[i + 1]
k-й сдвиг: a[i + k] если i + k < n, иначе a[i + k - n]
Видно, что эту операцию удобно выразить, как (i + k) % n. Тогда мы можем расписать S(A) (P.S. ^ -пусть будет возведением в степень)

S(A) = sum(sum(a[(i + k) % n] * 10^(n - 1 - i) for i in range(n - 1)) for k in range(n - 1))

Заметим, что мы можем заменить порядок суммирования и вынести 10^(n - 1 - i) и тогда под вторым знаком суммы будет фиксированная величина (а именно суммы всех цифр, обозначим её за Sum_dec), а степени десяток можно свернуть по формуле арифметической прогрессии.

S(A) = sum(sum(a[(i + k) % n] for k in range(n - 1)) * 10^(n - 1 - i) for i in range(n - 1)) =
sum(Sum_dec * 10^(n - 1 - i) for i in range(n - 1)) =
Sum_dec * (10^0 + 10^1 + 10^2 + … + 10^(n - 1)) =
Sum_dec * (10^n - 1) / 9 =
Sum_dec * 111…111 (n единиц)

Важное уточнение, последнюю величину можно вычислить сразу только на питоне (так как n слишком велико ~10^6, а в питоне есть длинку) и далее просто проссумировать все цифры. Для решения на с++ же, требуется реализовать простое умножение в столбик суммируя цифры в каждом десятке.

@algoses