История изменений

Какое то непонятное решение. Что за вычисления матричных произведений по модулю, да ещё и за 2log2 n шагов? Код покажете?

Объяснение. Берешь линейное реккурентное соотношение (по условию даны коэффициенты):
x[n+1] = a[0]*x[n]+...+a[k]*x[n-k],
и рассматриваешь вектор X_k такого вида:
X[k] = (x[k] x[k-1]... x[0])
и матрицу А строишь так, чтобы X[k+1] = X[k]*A: в первом столбце — коэффициенты уравнения («считаем очередное значение последовательности»), остальная матрица диагонально единицами заполнена от левого угла («сдвигаем вектор вправо, затирая ненужный x[0]»). Другими словами, в матричном виде записываешь действия, которые производятся при одной итерации линейного вычисления элементов последовательности. Если тебе надо посчитать x[n], то вместо того, чтобы множить вектор X[k] на матрицу (n-k) раз последовательно, возводишь ее в степень двоичным алгоритмом, а потом умножаешь вектор на нее.

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

Какое то непонятное решение. Что за вычисления матричных произведений по модулю, да ещё и за 2log2 n шагов? Код покажете?

Объяснение. Если записать в матричном виде обычное последовательное вычисление элементов последовательности, то в глаза бросается следующий трюк. В общем, берешь линейное реккурентное соотношение (по условию даны коэффициенты):
x[n+1] = a[0]*x[n]+...+a[k]*x[n-k],
и рассматриваешь вектор X_k такого вида:
X[k] = (x[k] x[k-1]... x[0])
и матрицу А строишь так, чтобы X[k+1] = X[k]*A: в первом столбце — коэффициенты уравнения («считаем очередное значение последовательности»), остальная матрица диагонально единицами заполнена от левого угла («сдвигаем вектор вправо, затирая ненужный x[0]»). Если тебе надо посчитать x[n], вместо того, чтобы множить вектор X[k] на матрицу (n-k) раз, возводишь ее в степень двоичным алгоритмом, а потом умножаешь вектор на нее.

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

Какое то непонятное решение. Что за вычисления матричных произведений по модулю, да ещё и за 2log2 n шагов? Код покажете?

Объяснение. Берешь линейное реккурентное соотношение:
x[n+1] = a[n]*x[n]+...+a[n-k]*x[n-k],
и рассматриваешь вектор X_k такого вида:
X[k] = (x[k] x[k-1]... x[0])
и матрицу А строишь так, чтобы X[k+1] = X[k]*A: в первом столбце — коэффициенты уравнения («считаем очередное значение последовательности»), остальная матрица диагонально единицами заполнена от левого угла («сдвигаем вектор вправо, затирая ненужный x[0]»). Если тебе надо посчитать x[n], вместо того, чтобы множить вектор X[k] на матрицу (n-k) раз, возводишь ее в степень двоичным алгоритмом, а потом умножаешь вектор на нее.

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