Во-второй можно, например, сначала разложить число в d-ичной системе счисления и записать в виде: d^k + d^k + d^k + d^(k — 1) + d^(k — 2)... А затем рекурсивно начать выносить за скобки максимально возможные степени d на всех префиксах разложения от конца до 1 (чтобы все степени вхождения d в скобке были >= 1).

Для d = 1 можно просто разложить число для d = 2, а затем представить все двойки как (1 + 1).

a[1] * d + d * (a[2] * d + d * (a[3] * d + d * (... Это разложение числа N в систему счисления по основанию d. a[i] — сколько d^i входит в число. Если a[i] == 0, то пропускаем это слагаемое. Иначе a[i] * d = d + d + ... + d — a[i] раз. Про d == 1 написали выше.

Как решать третью задачу?

Может кто-нибудь скинуть рабочий код к F?

Задача E:
У каждого палиндрома есть либо центр длины 1, если он нечетной длины, либо центр длины 2, если он четной длины. Таким образом строка является палиндромной только если найдется такое i, что s[i] = s[i+1] или s[i] = s[i+2].
Обозначим за F(x) количество антипалиндромных чисел, строго меньших x.
Тогда ответ на задачу F(R) — F(L) + good(R) (good(R) — 1 или 0 в зависимости от того, является число R антипалиндромным или нет).
Единственная сложность в том, чтобы посчитать F(x).
Если длина числа x равна 1, то все ясно.
Мы можем перебрать длину префикса, который будет общим для какого-то подходящего антипалиндромного числа и нашего числа x.
Пусть длина общего префикса 0. Тогда на первую позицию станет любая ненулевая цифра, меньшая, чем первая цифра в x. Количество таких цифр можно посчитать за О(1) и обозначить за C. На вторую позицию станет любая цифра, отличная от первой. На позиции 3 и дальше можно будет поставить любую цифру кроме последней и предпоследней поставленных. Итого получаем формулу: C * 35 * (34 ^ (len — 2)).
Теперь для ненулевой длины общего префикса.
Пусть мы зафиксировали эту длину — pref.
На позицию pref+1 подойдет любая цифра, которая меньше x[pref+1] и не равна 0, x[pref] и (x[pref-1] если pref>1). Количество таких цифр опять же можно посчитать за О(1) и обозначить за С.
Ну и по аналогии со случаем pref = 0, для каждой цифры правее будет ровно 34 варианта.
Суммируем количества по всем pref от 0 до len(x)-1, получаем какую-то часть F(x).
Мы забыли учесть числа, которые длиной меньше x.
Просто прибавим к значению F(x) значение dp[len(x) — 1], где dp[i] обозначает количество антипалиндромных чисел длиной до i включительно и считается следующим образом:
dp[i] = 36, i = 1
dp[i] = dp[1] + 35 * 36, i = 2
dp[i] = dp[i — 1] + 34 * dp[i-1], i > 2

С F(x) все. Как написать good(x), думаю, понятно)

Как решать задачу D?