Областная олимпиада по информатике 2020 год, 9-11 классы


Задача C. From And with love

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Абай очень любит массивы. Еще больше он любит играть с подпоследовательностями массива. Подпоследовательность — это такая последовательность массива, которая может быть получена удалением нескольких (возможно ноль) элементов из этого массива. Вам дан массив $A$ из $N$ целых чисел. Рассмотрим какую--нибудь подпоследовательность массива. Пусть битовый AND этой подпоследовательности равен $X$. Тогда подпоследовательность называется хорошей, если в ней нет элемента со значением $X$. Посчитайте количество хороших подпоследовательностей.
Формат входного файла
В первой строке дается натуральное число $N$ — размер массива $A$. В следующей строке заданы $N$ целых неотрицательных чисел — элементы массива $A$.
Формат выходного файла
Выведите одно число — количество хороших подпоследовательностей. Так как ответ может быть достаточно большим, выведите его остаток от деления на $10^9 + 7$.
Система оценки
Это задача состоит из 5 подзадач и 25 тестов, каждый тест оценивается в 4 балла:
  1. $1 <= N <= 15$, $0 <= A_i < 2^{20}$. Тесты 1 -- 3
  2. $1 <= N <= 10^5$, $0 <= A_i < 2^4$. Тесты 4 -- 7
  3. $1 <= N <= 10^5$, $0 <= A_i < 2^{10}$. Тесты 8 -- 12
  4. $1 <= N <= 10^5$, $0 <= A_i < 2^{15}$. Тесты 13 -- 18
  5. $1 <= N <= 10^6$, $0 <= A_i < 2^{20}$. Тесты 19 -- 25
Пример:
Вход
5
0 2 5 3 7
Ответ
6
Замечание
Одной из хороших подпоследовательностей является 2, 5, 7. Ее битовый AND равен 0, при этом число 0 не присутствует среди 2, 5, 7. Операция побитового AND существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как <<$\string&$>>, в Pascal — как <>. Таблица для побитового AND.\\ 1 $and$ 1 = 1, 1 $and$ 0 = 0\\ 0 $and$ 1 = 0, 0 $and$ 0 = 0\\ ( Abay Baimukanov )
посмотреть в олимпиаде

Комментарий/решение:

  0
2022-01-04 16:25:37.0 #

показать/скрыть код