Codeforces Round 953 (Div. 2) |
---|
Закончено |
Дан массив $$$a$$$ длины $$$n$$$. Построим квадратную матрицу $$$b$$$ размера $$$n \times n$$$, где в $$$i$$$-й строке записан массив $$$a$$$, циклически сдвинутый на $$$(i - 1)$$$ вправо. Например, для массива $$$a = [3, 4, 5]$$$ получается матрица
$$$$$$b = \begin{bmatrix} 3 & 4 & 5 \\ 5 & 3 & 4 \\ 4 & 5 & 3 \end{bmatrix}$$$$$$
Построим следующий граф:
Ваша задача — посчитать количество компонент связности$$$^{\dagger}$$$ в полученном графе.
$$$^{\dagger}$$$Компонента связности графа — это множество некоторых вершин графа, в котором любая вершина достижима из любой по рёбрам, и добавление любой другой вершины в множество нарушает это правило.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 10^6$$$, $$$2 \le k \le 2 \cdot 10^6$$$) — длина массива и параметр $$$k$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — элементы массива $$$a$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите одно целое число — количество компонент связности в полученном графе.
63 33 4 53 33 4 93 23 4 92 22 85 38 27 5 4 34 102 2 2 2
3 2 3 1 4 1
В первом наборе входных данных матрица $$$b$$$ приведена в условии. Первая компонента связности содержит вершины $$$(1, 1)$$$, $$$(2, 2)$$$ и $$$(3, 3)$$$. Вторая компонента связности содержит вершины $$$(1, 2)$$$, $$$(2, 3)$$$ и $$$(3, 1)$$$. Третья компонента связности содержит вершины $$$(1, 3)$$$, $$$(2, 1)$$$ и $$$(3, 2)$$$. Таким образом, в графе есть $$$3$$$ компоненты связности.
Во втором наборе входных данных получается следующая матрица:
$$$$$$b = \begin{bmatrix} 3 & 4 & 9 \\ 9 & 3 & 4 \\ 4 & 9 & 3 \end{bmatrix}$$$$$$
Первая компонента связности содержит все вершины, соответствующие элементам со значениями $$$3$$$ и $$$9$$$. Вторая компонента связности содержит все вершины, соответствующие элементам со значением $$$4$$$.
В четвёртом наборе входных данных все вершины находятся в одной компоненте связности.
Название |
---|