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

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

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

Абай массивтерді өте жақсы көреді. Әсіресе массивтің тізбекшелерімен ойнағанды ұнатады. Тізбекше — ол массивтен бірнеше(мүмкін 0) элементтің өшіру арқылы алынатын сандар тізбегі. Сізге $N$ саннан тұратын $A$ массивы беріледі. Массивтің кез-келген бір тізбегін қарастырайық. Олардың биттік AND $X$-қа тең болсын. Тізбекше жақсы деп аталады, егер тізбекте $X$-ке тең сан болмаса. Массивтегі жақсы тізбекшелердің саның табыңыз.

Формат входного файла

Бірінші жолда бір бүтін сан $N$ — $A$ массивының размері берілген. Келесі жолда $N$ бүтін теріс емес сандар берілген — $A$ массивының элементтері.

Формат выходного файла

Жалғыз бүтін сан шығарыңыз — жақсы тізбекшелердің саның. Жауап өте үлкен болуы мүмкін, сол себептен оның $10^9 + 7$ге бөлгендегі қалдығын шығарыңыз.

Система оценки

Есеп 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 осы тізбекте жоқ . Биттік AND операциясы барлық заманауи бағдарламалау тілдерінде бар, С++ және 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))