Я знаю, что это скорее вопрос теории сложности, чем вопрос программирования, надеюсь, я не ошибаюсь, пишу здесь, извиняюсь, если это не то место, но я надеюсь, что кто-то из вас найдет ответ. И это даже в какой-то мере связано с тем, что программа является вопросом теории сложности.
Я изучаю линейные повторяющиеся последовательности, и я прочитал, что для получения n-го значения последовательности, которое выскочило, необходимо получить некоторую степень сопутствующей матрицы, мне было интересно, есть ли известный алгоритм быстро получить полномочия такого рода матриц ..
Я не могу привести пример кодирования, но постараюсь дать вам более подробное объяснение:
Однородная линейная повторяющаяся последовательность k-го порядка:
s (n + k) = a (k-1) s (n + k-1) + a (k-2) s (n + k-2) + ... + a (0)
для n = 0,1, .. где s (i) - i-ое значение последовательности, а a (i) - коэффициенты в алгебраическом поле.
A - это сопутствующая матрица вышеуказанной последовательности, если она:
(0 0 0 0 ... 0 a (0))
(1 0 0 0 ... 0 a (1))
(0 1 0 0 ... 0 a (2))
(.. .. .. .. .. .. .. .. ..)
(0 0 0 0 ... 1 a (k-1))
Более того, теория утверждает, что для векторов состояния последовательности имеем:
s (n) = s (0) A ^ n для n = 0,1, ..
Вот и все, спасибо за помощь.