Областная олимпиада по информатике 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 )

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

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

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const ll N = 1e7;

ll n,  cnt = 0, ans = 0;
ll a[N];

int main(){
	cin >> n;
	ll tmp = 2080981;
	for(ll i = 1; i<=n; i++){
		cin >> a[i];
	}
	
	for(ll i = 1; i<=n; i++){
		cnt = 0;
		tmp &= a[i];
		for(ll j = i+1; j<=n; j++){
			if(a[j] == tmp) break;
			else cnt++;
		}
		if(cnt == n - i) ans++;
	}
	
	tmp = 2080981;
	cnt = 0;

	for(ll i = 1; i<=n; i++){
		for(ll j = i; j<=n; j++){
			tmp &= a[j];
		}
		for(ll j = 1; j<=n; j++){
			if(a[j] == tmp) break;
			else cnt++;
		}
		if(cnt == n) ans++;
		tmp = 2080981;
	}
	cout << ans;
}

Как это емае работает..

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

import itertools
import functools
import operator
from itertools import combinations, starmap

n = int(input())


data = list(map(int, input().split()))


d = ([list(filter(lambda x: 0 not in x, combinations(data, i))) for i in range(2, len(data))])
# y = list(filter(lambda x: len(x) > 1, map(data.__getitem__, starmap(slice, combinations(range(len(data)+1), 2)))))

c= 0
for i in d:
    for j in i:
        # print(j,  functools.reduce(lambda x, y: x & y, j))
        if functools.reduce(lambda x, y: x & y, j) not in j:
            c += 1
# print(list(itertools.product(data, [data])))
print(c % (pow(10, 9) + 7))
# print(help(itertools))

Сложность O(n * log(n))