Пытаюсь решить задачку, закопался.

Вкратце, нужно найти количество N-значных чисел, у которых абсолютная разность между любыми двумя соседними цифрами не меньше K.
Ограничения: 2 ≤ N ≤ 10⁹, 0 ≤ K ≤ 9. Ответ нужно посчитать по модулю 10⁹ + 7.

Попробовал вывести рекуррентные формулы для количества комбинаций из i разрядов, а затем, так как ограничения довольно внушительные, находить ответ путем возведения матрицы перехода в степень.

Формулы получились следующие:
K = 9: F_i = F_i – 1 = 1 (ведущих нулей быть не должно, поэтому единственный возможный вариант 90909...)
K = 8: F_i = F_i – 1 + F_i – 2 (как Фибоначчи, только с другими начальными значениями, которые можно считать, например, перебором)
K = 7: F_i = 2·F_i – 1 + F_i – 2 – F_i – 3
K = 6: F_i = 2·F_i – 1 + 3·F_i – 2 – F_i – 3 – F_i – 4
K = 5: F_i = 3·F_i – 1 + 3·F_i – 2 – 4·F_i – 3 – F_i – 4 – F_i – 5

Далее становится чуть сложнее, например, при K = 4 от цифры 5 возможные варианты продолжения — 0, 1 и 9, и не очень понятно, как теперь меняется количество комбинаций.

Такое ощущение, что у этой задачи есть более простое решение, прошу поделиться или намекнуть.

Привет!
Пытаюсь решить следующую задачу, найденную на одном из форумов:

Две строки могут быть перемешаны путем вставки символов первой строки между символами второй (с сохранением их порядка). Рассмотрим перемешивание двух одинаковых строк - близнецов.

Например, строка AAABAB может быть получена путем перемешивания двух строк AAB.

Дается строка, необходимо определить, могла ли она быть получена путем перемешивания двух некоторых строк-близнецов.  
(другими словами, можно ли вычеркнуть половину символов так, чтобы строки, образованные вычеркнутыми и оставшимися символами, совпадали)

Логичная предпроверка: необходима четность каждого символа (XOR всех символов == 0).
Далее, ничего не удается придумать, кроме полного рекурсивного перебора O(2^N) :(

Как можно решить задачу более эффективно?