Условие:
Условие задачи
Гистограммой является массив, каждый элемент которого указывает высоту столбика на соответствующей позиции.
Две гистограммы считаются совпадающими, если при совмещении одной гистограммы с другой гистограммой, повёрнутой на угол 180°, получается ровный прямоугольник без наложений и пропусков. Более формально: две гистограммы
a
a
и
b
b
называются совпадающими, если
a
i
+
b
m
−
i
+
1
=
a
j
+
b
m
−
j
+
1
a
i
+b
m−i+1
=a
j
+b
m−j+1
для любой пары
(
i
,
j
)
(i,j)
(
1
≤
i
,
j
≤
m
)
(1≤i,j≤m)
.
Даны
N
N
гистограмм длины
M
M
, необходимо найти количество пар совпадающих гистрограмм.
Входные данные
Каждый тест состоит из нескольких наборов входных данных.
Первая строка содержит целое число
t
t
(
1
≤
t
≤
1
0
5
)
(1≤t≤10
5
)
— количество наборов входных данных.
В первой строке каждого набора входных данных даны числа
N
N
и
M
M
.
N
N
обозначает количество различных гистограмм,
M
M
— их длину
(
2
≤
N
,
M
≤
1
0
5
)
.
(2≤N,M≤10
5
).
Гарантируется, что сумма
N
⋅
M
N⋅M
по всем тестам не больше
1
0
5
10
5
.
Каждая из следующих
N
N
строк содержит
M
M
целых неотрицательных чисел. Все числа не превосходят
1
0
9
10
9
.
Группы
тестов
Группытестов
doschechki-groups
Выходные данные
Для каждого набора входных данных выведите число — количество пар совпадающих гистограмм.
Иллюстрация
Иллюстрация
На картинке пример пар совпадающих и несовпадающих гистограмм:
histo-picture
Пример теста 1
Входные данные
3
3 3
1 2 4
1 3 4
1 4 3
3 4
1 3 2 4
1 3 2 4
2 4 3 5
2 2
1 2
2 1
Выходные данные
1
3
0
реши задачу на golang