Блог пользователя igor.pisarev

Автор igor.pisarev, 10 лет назад, По-русски

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

Вкратце, нужно найти количество 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, и не очень понятно, как теперь меняется количество комбинаций.

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

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

Возведение матрицы в степень. В матрице пишем a[i][j]=1, если цифры i и j могут быть соседними, и 0 в противном случае.

Пускай у нас есть вектор размера 10, в котором i-ый элемент равен количеству хороших чисел длины 1, у которых последняя (и единственная, в нашем случае) цифра равна i. Умножив этот вектор на нашу матрицу, получим аналогичный вектор, который отвечает за числа длины 2; умножив еще раз — вектор, который отвечает за числа длины 3. Поскольку умножение ассоциативно, то сначала быстрым возведением в степень посчитаем нужную матрицу, а потом уже умножим на нее наш начальный вектор.

»
10 лет назад, # |
Rev. 8   Проголосовать: нравится +3 Проголосовать: не нравится

For k = 4, {3, 8, -6, -6} which mean

Fn = 3Fn - 1 + 8Fn - 2 - 6Fn - 3 - 6Fn - 4

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.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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.