Блог пользователя nicenicenice

Задача на матрицы
Автор nicenicenice, история, 11 лет назад, По-русски

Здравствуй, Сodeforces! Решаю одну задачу на умножение матриц. Не проходит один из тестов по времени. Подскажите пожалуйста, как можно оптимизировать? Вот мой код.

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

»
11 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

Идея такая (не проверял):

Составим вектор-столбец B размера n из нулей. Но на b-й позиции еденица.

Тогда ответ — это a-е число вектора A1 * A2 * ... * Am * B.

Заметим, что это можно считать не слева направо, а справа налево.

Тогда сложность будет в n раз меньше. Вроде ничего не упустил.

→ Ответить
  • »
    »
    11 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо за ответ, но никак не могу понять реализацию. Можете привести небольшой фрагмент кода или псевдо-код. Все-таки новичок, еще многого не понимаю. И можно еще по-подробнее про вектор-столбец.

    → Ответить