Здравствуйте, Кузнец, Вы писали:

К> то сложность возведения матрицы в степень будет n*n*n * log(N) (используем бинарное возведение в степень), при n = 2000 это слишком много (кубическая сложность).
Матрицы в квадрат можно и не за куб возводить. Тем же алгоритмом Винограда—Штрассена, например. Не квадратичная сложность, но всё же.