Изменения
Нет описания правки
Таким образом, при подстановке <tex>k = \log n</tex>, получаем итоговую трудоёмкость <tex dpi=140>O(n^2 \log n) + O(\frac{n^3}{\log n}) = O(\frac{n^3}{\log n})</tex>
== Код алгоритма ==
<code>
int n, cur;
vector <vector <int> > a, b, preculc, anew, bnew, ans;
int main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> n;
a.resize(n);
b.resize(n);
ans.resize(n);
// Чтение матриц
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
cin >> cur;
a[i].push_back(cur);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
cin >> cur;
b[i].push_back(cur);
}
// Предподсчёт скалярных произведений
int k = ceil(log( (double) n));
preculc.resize(1 << k);
for (int i = 0; i < (1 << k); i++)
for (int j = 0; j < (1 << k); j++) {
int scalmul = 0;
for (int pos = 0; pos < k; pos++)
if (((1 << pos) & i) != 0 && ((1 << pos) & j) != 0) {
scalmul = (scalmul + 1) % 2;
}
preculc[i].push_back(scalmul);
}
// Создание сжатых матриц
int m = ceil(((double) n) / k);
anew.resize(n);
bnew.resize(m);
for (int i = 0; i < n; i++) {
for (int start = 0; start < n; start += k) {
int cursuma = 0, cursumb = 0, curpos = start, deg = (1 << (k - 1));
while (curpos < start + k && curpos < n) {
cursuma += a[i][curpos] * deg;
cursumb += b[curpos][i] * deg;
deg /= 2;
curpos++;
}
anew[i].push_back(cursuma);
bnew[start / k].push_back(cursumb);
}
}
//Перемножение полученных матриц
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
int curans = 0;
for (int pos = 0; pos < m; pos++) {
curans = (curans + preculc[anew[i][pos]][bnew[pos][j]]) % 2;
}
ans[i].push_back(curans);
}
// Вывод ответа
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << ans[i][j] << " ";
}
cout << endl;
}
return 0;
}
</code>
