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

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

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

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

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

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

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

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

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

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

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

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

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

      Например, а = 3, b = 1. Ответ — 95.

      Тогда

      Смотрим что на 3-й позиции — там 95

      → Ответить