Я обрисую достаточно, чтобы вы пошли. Но у вас уйдет большая часть работы.
Обратите внимание, что благодаря симметрии после любого числа оборотов число способов наматывания при любом конкретном значении, отличном от 1, равнозначно намотке на любом другом , Следовательно, если x_m_l - это число способов построить настолько действительную последовательность, которая с шагом m заканчивается на l, тогда x_m_2 == x_m_3 == ... == x_m_k. Но x_m_1 может быть другим. Итак, давайте назовем x_m_1 x_m и остальных y_m.
У нас сразу же есть x_0 = 1 и y_0 = 0. После небольшой мысли мы имеем x_(m+1) = (k-1) * y_m. И y_(m+1) = x_m + (k-2) * y_m.
Запись того, что в качестве вектора (извините за плохое искусство ASCII) первое выглядит так:
( x_0 ) -- ( 1 )
( y_0 ) -- ( 0 )
А второе превращается в следующее матричное уравнение:
( x_(m+1) ) -- [ 0 k-1 ] ( x_m )
( y_(m+1) ) -- [ 1 k-2 ] ( y_m )
Пока все хорошо. Но давайте назовем эту матрицу перехода T. Это продвигает нас вперед на один шаг. Но если вы хотите продвинуться на 2 шага, вы можете просто умножить на T дважды. T^2. 3 шага вам просто нужно T^3. И так далее.
В результате T^m является матрицей для продвижения вперед m шагов. И T^n содержит ваш ответ. (Если вы посмотрите на первую или вторую записи в векторе, зависит от того, j=1 или что-то еще.)
Если вы просто вычисляете T^n путем многократного умножения (выполняя арифметику по модулю c), вы получите желаемый ответ.
Если вы умны в отношении повторного возведения в квадрат, вы можете решить его в логарифмическом c времени.
Для связанных топи c см. https://medium.com/@andrew.chamberlain /-линейная алгебра ракурса-оф-последовательность Фибоначчи-4e81f78935a3