Ограничение времени | 3 секунды |
Ограничение памяти | 256 Мб |
Ввод | стандартный ввод |
Вывод | стандартный вывод |
В этой задаче на проверку необходимо сдать программу, которая будет решать поставленную задачу.
Большие языковые модели (Large language model, LLM) в своей основе имеют операцию умножения квадратных матриц. Вася узнал, что в одной из популярных LLM используется возведение в квадрат квадратных 0-1 матриц.
Квадратная 0-1 матрица — это двумерный массив размером , состоящий из чисел 0 и 1. В результате возведения матрицы в квадрат получается квадратная матрица того же размера , элементы которой вычисляются по следующей формуле:
, где — это операция взятия остатка.
Васе удалось получить результирующие матрицы . Для создания своей модели он хочет провести реверс-инжиниринг и найти такую матрицу , что . Помогите ему.
В первой строке вводится число ( ) — количество матриц, для которых нужно найти квадратный корень.
Далее следует блоков с описанием матрицы.
В первой строке каждого блока содержится число ( ) — размер матрицы. В следующих строках содержится по чисел 0 и 1, задающих матрицу.
Выведите матриц, являющихся квадратным корнем заданной. Разделяйте матрицы пустой строкой.
Если вы не можете определить квадратный корень для какой-либо матрицы — выведите строк, состоящих из нулей, где соответствует размеру исходной матрицы.
Ввод | Вывод |
---|---|
2 3 1 0 0 0 1 0 0 0 1 3 0 1 0 0 1 0 0 1 0 | 0 0 1 1 1 1 1 0 0 0 1 0 0 1 0 1 0 0 |
Оценка за эту задачу — 50 баллов, тестирование проводится онлайн (после тура баллы за задачу не изменятся).
Каждая верно найденная матрица оценивается в 2 балла.