Изменения
Нет описания правки
{{Задача|definition = Дано две квадратных матрицы <tex>A_{[n \times n]}</tex> и <tex>B_{[n \times n]}</tex>,
состоящие из нулей и единиц. Нужно найти их произведение. При этом, все операции выполняются по модулю <tex>2</tex>.
}}</noinclude><includeonly>{{#if: {{{neat|}}}|<div style="background-color: #fcfcfc; float:left;"><div style="background-color: #ddd;">'''Задача:'''</div><div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;">{{{definition}}}</div></div>|<table border="0" width="100%"><tr><td style="background-color: #ddd">'''Задача:'''</td></tr><tr><td style="border:1px dashed #2f6fab; padding: 8px; background-color: #fcfcfc; font-style: italic;">{{{definition}}}</td></tr></table>}}</includeonly>
== Простое решение ==
* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.
* Создание матриц <tex>A'</tex> и <tex>B'</tex> {{---}} <tex>O(n^2)</tex>.* Перемножение полученных матриц {{---}} <tex>O(\dfrac{n^3}{k})</tex>.
Итого: <tex>O(2^{2k}k) + O(\dfrac{n^3}{k})</tex>.
<tex>
\begin{tabulararray}{|c|c|c|c|c|}
\hline
& \textbf{00} & \textbf{01} & \textbf{10} & \textbf{11} \\
\textbf{11} & 0 & 1 & 1 & 0\\
\hline
\end{tabulararray}
</tex>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]
[[Категория: Способы оптимизации методов динамического программирования]]
