Задача №114748. Уничтожение массива
Дан массив \(a_1, a_2, \ldots, a_n\), состоящий из целых чисел.
Определим операцию «уничтожения» с целочисленным параметром \(k\) (\(1 \leq k \leq n\)):
- Выбрать \(k\) различных индексов массива \(1 \leq i_1 < i_2 < \ldots \leq i_k\).
- Вычислить \(x = a_{i_1} ~ \text{AND} ~ a_{i_2} ~ \text{AND} ~ \ldots ~ \text{AND} ~ a_{i_k}\), где \(\text{AND}\) это операция побитового «И» (обратитесь к тексту в конце условия для формального определения).
- Вычесть \(x\) из всех \(a_{i_1}, a_{i_2}, \ldots, a_{i_k}\) и оставить остальные элементы массива без изменения.
Найдите все значения \(k\), для которых с помощью конечного количества операций уничтожения с параметром \(k\) можно сделать все элементы массива равными \(0\). Можно показать, что для любого массива \(a\) существует хотя бы одно подходящее \(k\).
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится целое число \(t\) (\(1 \leq t \leq 10^4\)) — количество наборов входных данных. Далее следуют описания наборов входных данных.
В первой строке описания каждого набора входных данных находится целое число \(n\) (\(1 \leq n \leq 200\,000\)).
В следующей строке находится \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(0 \leq a_i < 2^{30}\)).
Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(200\,000\).
Для каждого набора входных данных выведите все значения \(k\), для которых с помощью операций уничтожения можно сделать все элементы массива равными \(0\). Вы должны вывести их в возрастающем порядке.
В первом наборе входных данных:
- При \(k = 1\) мы можем сделать четыре операции уничтожения с наборами индексов \(\{1\}\), \(\{2\}\), \(\{3\}\), \(\{4\}\). При каждой из этих операций число на соответствующем индексе занулится.
- При \(k = 2\) мы можем сделать две операции уничтожения с наборами индексов \(\{1, 2\}\), \(\{3, 4\}\). При каждой из этих операций числа на соответствующих индексах будут зануляться.
- При \(k = 3\) невозможно сделать все \(a_i\) равными \(0\). Если мы сделаем любую операцию уничтожения в самом начале, то в нашем массиве три числа станет равными \(0\) и одно число останется равным \(4\). После этого любая операция уничтожения не будет изменять массив, потому что среди индексов, которые используются, будет индекс, значение массива для которого равно \(0\).
- При \(k = 4\) мы можем сделать одну операцию уничтожения с набором индексов \(\{1, 2, 3, 4\}\).
Во втором наборе входных данных при \(k = 2\) мы можем сделать следующие операции уничтожения:
- Операция с индексами \(\{1, 3\}\). Из элементов на этих индексах вычитается \(9 = 13 ~ \text{AND} ~ 25\). Массив после операции станет \([4, 7, 16, 19]\).
- Операция с индексами \(\{3, 4\}\). Из элементов на этих индексах вычитается \(16 = 16 ~ \text{AND} ~ 19\). Массив после операции станет \([4, 7, 0, 3]\).
- Операция с индексами \(\{2, 4\}\). Из элементов на этих индексах вычитается \(3 = 7 ~ \text{AND} ~ 3\). Массив после операции станет \([4, 4, 0, 0]\).
- Операция с индексами \(\{1, 2\}\). Из элементов на этих индексах вычитается \(4 = 4 ~ \text{AND} ~ 4\). Массив после операции станет \([0, 0, 0, 0]\).
Формальное определение побитового «И»
Определим операцию побитового «И» (AND). Пусть даны два целых неотрицательных числа \(x\) и \(y\), рассмотрим их двоичные записи (возможно с ведущими нулями): \(x_k \dots x_2 x_1 x_0\) и \(y_k \dots y_2 y_1 y_0\). Здесь \(x_i\) это \(i\)-й бит числа \(x\), а \(y_i\) это \(i\)-й бит числа \(y\). Пусть \(r = x ~ \text{AND} ~ y\) — результат операции AND над числами \(x\) и \(y\). Тогда двоичной записью \(r\) будет \(r_k \dots r_2 r_1 r_0\), где:
\(\) r_i = \begin{cases} 1, ~ \text{если} ~ x_i = 1 ~ \text{и} ~ y_i = 1 \\ 0, ~ \text{если} ~ x_i = 0 ~ \text{или} ~ y_i = 0 \end{cases} \(\)
5 4 4 4 4 4 4 13 7 25 19 6 3 5 3 1 7 1 1 1 5 0 0 0 0 0
1 2 4 1 2 1 1 1 2 3 4 5