Изменения
Нет описания правки
// Предподсчёт скалярных произведений
// Пусть precalc[i][j] - "скалярное произведение для битовых представлений" чисел i и j
// "&" - битовый and; "<<" - битовый сдвиг влево.
int k = ceil(log n); //округление вверх
for i := 0 to (1 << k) - 1
int scalmul = 0;
for pos := 0 to k - 1
if (((1 << pos) & i) != 0 && and ((1 << pos) & j) != 0) { scalmul = (scalmul + 1) % mod 2;
}
precalc[i][j] = scalmul;
}
// Создание сжатых матрицanew, bnew for I i := 0 to n - 1 { для всех стартовых позиций while (start группы из k элементов < n) { Представляем текущую двоичную последовательность в текущей строке I матрицы A как десятичное число.int cursuma = 0, cursumb = 0, curpos = start, deg = (1 << (k - 1)); Записываем полученное значение в A'.while (curpos < start + k and curpos < n) { } cursuma += a[i][curpos] * deg; } cursumb += b[curpos][i] * deg; for J deg /= 0 to n - 1 {2; curpos++; } для всех стартовых позиций anew[i][start группы из div k элементов {](cursuma); Представляем текущую двоичную последовательность в текущем столбце J матрицы B как десятичное число.bnew[start div k][i](cursumb); Записываем полученное значение в B'.start = start + k;
}
}
//Перемножение полученных матриц
for i := 0 to n - 1
