Изменения
Нет описания правки
// Предподсчёт скалярных произведений
// Пусть precul[I][J] - "скалярное произведение для битовых представлений" чисел I и J
k = log n
for I = 0 to 2^k - 1 do
for J = 0 to 2^k - 1 do {
Считаем скалярное произведение двоичных векторов, заданных двоичным представлением чисел I и J.
Записываем результат в матрицу preculc, где precul[I][J] - "скалярное произведение для битовых представлений" I и J.
}
// Создание сжатых матриц
for I = 0 to n - 1 {
для всех стартовых позиций группы из k элементов start {
Считаем сумму в горизонтальной группе матрицы aA, которая начинается с позиции start, и записываем десятичное значение полученного двоичного представления в аA'. Считаем сумму в вертикальной группе матрицы bB, которая начинается с позиции start, и записываем десятичное значение полученного двоичного представления в bB'.
}
}
for I = 0 to n - 1 do
for J = 0 to n - 1 do {
Считаем сумму по модулю 2 всех произведений группы чисел из k элементовпроизведение I строки A' и J столбца B', пользуясь предподсчётом preculc.
Записываем полученное значение в матрицу ответа.
}
