Пытаюсь решить задачку, закопался.
Вкратце, нужно найти количество N-значных чисел, у которых абсолютная разность между любыми двумя соседними цифрами не меньше K.
Ограничения: 2 ≤ N ≤ 109, 0 ≤ K ≤ 9. Ответ нужно посчитать по модулю 109 + 7.
Попробовал вывести рекуррентные формулы для количества комбинаций из i разрядов, а затем, так как ограничения довольно внушительные, находить ответ путем возведения матрицы перехода в степень.
Формулы получились следующие:
K = 9: Fi = Fi – 1 = 1 (ведущих нулей быть не должно, поэтому единственный возможный вариант 90909...)
K = 8: Fi = Fi – 1 + Fi – 2 (как Фибоначчи, только с другими начальными значениями, которые можно считать, например, перебором)
K = 7: Fi = 2·Fi – 1 + Fi – 2 – Fi – 3
K = 6: Fi = 2·Fi – 1 + 3·Fi – 2 – Fi – 3 – Fi – 4
K = 5: Fi = 3·Fi – 1 + 3·Fi – 2 – 4·Fi – 3 – Fi – 4 – Fi – 5
Далее становится чуть сложнее, например, при K = 4 от цифры 5 возможные варианты продолжения — 0, 1 и 9, и не очень понятно, как теперь меняется количество комбинаций.
Такое ощущение, что у этой задачи есть более простое решение, прошу поделиться или намекнуть.
Возведение матрицы в степень. В матрице пишем a[i][j]=1, если цифры i и j могут быть соседними, и 0 в противном случае.
Пускай у нас есть вектор размера 10, в котором i-ый элемент равен количеству хороших чисел длины 1, у которых последняя (и единственная, в нашем случае) цифра равна i. Умножив этот вектор на нашу матрицу, получим аналогичный вектор, который отвечает за числа длины 2; умножив еще раз — вектор, который отвечает за числа длины 3. Поскольку умножение ассоциативно, то сначала быстрым возведением в степень посчитаем нужную матрицу, а потом уже умножим на нее наш начальный вектор.
Здорово и понятно.. Спасибо
For k = 4, {3, 8, -6, -6} which mean
For k = 3, {3, 15, 2, -1}
For k = 2, {4, 22, 11, -14, -3}
For k = 1, I am getting lazy now. But it is look like $F_n = 9 * F_{n - 1}$
k = 0, Fn = Fn - 1 = 9 of course.
P/S: Please help me check my result, my pencil and paper skill may contain bugs.
Naive program for checking all untested formulas above.
Happy Programmers' day, I have a party with some (github) friend now, I will check above solution later.
Update 0: tested, look correct from here.