Сборник Олпрогера

Матрицы и их умножение

Предисловие:
Вам не нужно знать все о матрицах, чтобы пользоваться ими на олимпиадах) Курс линейной алгебры тут не нужен

Достаточно этого:
* Матрица - это двумерный (одно из измерений может быть равно единице) набор чисел
* Как работает умножение матриц: суть, алгориитм и время его работы

И дальше нужно научиться видеть (через решение задач естественно), где можно задачу свести к умножению матриц или возведению матрицы в степень. В последнем случае можно получить ускорение за счет бинарного возведения в степень, с матрицами этот трюк тоже работает.
Это может пригодиться, например, в пересчете ДП. А самым базовым примером является задача нахождения n-го числа Фибоначчи быстрее чем O(n)😱 Как это возможно, узнаете ниже)

Пререквизиты:
🔙 Сумма, вычитание, произведение, деление по модулю
🔙 Бинарное возведение в степень
🔙 Базовое ДП

Теория:
📚 Алгоритмика 1 - определение матриц и их умножения + код умножения
📚 Алгоритмика 2 - как использовать умножение матриц в задачах, n-ое число Фибоначчи и другие задачи
📼 Видео от красного на кф Errichto (На английском) - очень подробное объяснение как решать несколько задач на тему

KIT контест по теме с периодически пополняемыми задачами:
🔄 Контест - в этот раз просто взял контест от Errichto, очень он хорош для отработки: простые и сложные задачки. Для решения нужно вступить в группу на кф - ссылка

Вопросы на понимание темы:
❓ За какое время работает умножение матрицы размером NxK на матрицу размером KxM?
❗️ O(N * M * K)

❓ Что делать, если в реккуренту затесалась константа? Например, a2 = a1 + a0 + 5. Как тогда посчитать n-ое значение с помощью умножения матриц?
❗️Как минимум 2 способа. 1) Немного отойти от общего случая (как в алгоритмике 2 описано) и составить немного другую матрицу - пишите в комментах какую. 2) Избавиться от этой константы. Можно из a3 вычесть a2, тогда константа (5) сократится и получится новая реккурента. Ее уже общим случаем можно спокойно решить

Автор: https://www.tgoop.com/KogutIvanTutoring

Теги: #алгоритмы #матрицы

Please open Telegram to view this post

VIEW IN TELEGRAM

👍23👎4

www.tgoop.com/sbornik_olprog/192

3.5K viewsNikolay Khadzakos, edited  Mar 30, 2024 at 06:25

Матрицы и их умножение

Предисловие:
Вам не нужно знать все о матрицах, чтобы пользоваться ими на олимпиадах) Курс линейной алгебры тут не нужен

Достаточно этого:
* Матрица - это двумерный (одно из измерений может быть равно единице) набор чисел
* Как работает умножение матриц: суть, алгориитм и время его работы

И дальше нужно научиться видеть (через решение задач естественно), где можно задачу свести к умножению матриц или возведению матрицы в степень. В последнем случае можно получить ускорение за счет бинарного возведения в степень, с матрицами этот трюк тоже работает.
Это может пригодиться, например, в пересчете ДП. А самым базовым примером является задача нахождения n-го числа Фибоначчи быстрее чем O(n)😱 Как это возможно, узнаете ниже)

Пререквизиты:
🔙 Сумма, вычитание, произведение, деление по модулю
🔙 Бинарное возведение в степень
🔙 Базовое ДП

Теория:
📚 Алгоритмика 1 - определение матриц и их умножения + код умножения
📚 Алгоритмика 2 - как использовать умножение матриц в задачах, n-ое число Фибоначчи и другие задачи
📼 Видео от красного на кф Errichto (На английском) - очень подробное объяснение как решать несколько задач на тему

KIT контест по теме с периодически пополняемыми задачами:
🔄 Контест - в этот раз просто взял контест от Errichto, очень он хорош для отработки: простые и сложные задачки. Для решения нужно вступить в группу на кф - ссылка

Вопросы на понимание темы:
❓ За какое время работает умножение матрицы размером NxK на матрицу размером KxM?
❗️ O(N * M * K)

❓ Что делать, если в реккуренту затесалась константа? Например, a2 = a1 + a0 + 5. Как тогда посчитать n-ое значение с помощью умножения матриц?
❗️Как минимум 2 способа. 1) Немного отойти от общего случая (как в алгоритмике 2 описано) и составить немного другую матрицу - пишите в комментах какую. 2) Избавиться от этой константы. Можно из a3 вычесть a2, тогда константа (5) сократится и получится новая реккурента. Ее уже общим случаем можно спокойно решить

Автор: https://www.tgoop.com/KogutIvanTutoring

Теги: #алгоритмы #матрицы