Bit Problem

Explicación

Un enfoque de fuerza bruta, para cada elemento $x$ , iteraría sobre todos los demás elementos $y$ y verificaría las tres condiciones. Esto resulta en tiempo $\mathcal{O}(N^2)$ , que es demasiado lento.

Entendamos las relaciones:

$x \, \mid \, y = x \implies$ $y$ es una submáscara de $x$
$x \mathbin{\&} y = x \implies$ $y$ es una supermáscara de $x$
$x \mathbin{\&} y \neq 0 \implies$ $y$ no es disjunto con $x$

Como los valores son a lo sumo $2^{20}$ , tratamos cada número como una máscara de 20 bits y construimos un arreglo de frecuencias.

Ahora el problema se reduce a:

Para cada máscara, contar cuántas de sus submáscaras aparecen.
Para cada máscara, contar cuántas de sus supermáscaras aparecen.

Hacer esto de forma naive iterando sobre las submáscaras de cada $x$ toma hasta $3^{20}$ operaciones, lo cual es inviable.

En su lugar, aplicamos SOS DP.

Cómo funcionan las transiciones de SOS DP

Inicializamos tanto dp como kp con la frecuencia de cada máscara.

dp[mask] se convertirá en el número de elementos del arreglo que son submáscaras de mask.
kp[mask] se convertirá en el número de elementos del arreglo que son supermáscaras de mask.

DP de submáscaras

Para cada bit i y cada mask:

Si el bit i está activado en mask, entonces cualquier submáscara de mask o bien:

no usa el bit i, o
sí usa el bit i.

Las submáscaras que no usan el bit i corresponden exactamente a mask ^ (1 << i). Así que acumulamos:


if (mask & (1 << i)) dp[mask] += dp[mask ^ (1 << i)];

Después de procesar todos los bits, dp[mask] es igual al número total de elementos que son submáscaras de mask.

DP de supermáscaras

Simétricamente, si el bit i no está activado en mask, entonces las supermáscaras de mask que incluyen el bit i corresponden a mask ^ (1 << i). Así que acumulamos:


if (!(mask & (1 << i))) kp[mask] += kp[mask ^ (1 << i)];

Después de procesar todos los bits, kp[mask] guarda el número de elementos que son supermáscaras de mask.

Ambos cálculos corren en $\mathcal O(B \cdot 2^B)$ .

Derivar la tercera respuesta

Necesitamos el conteo de y tales que:

x & y != 0

En su lugar, contamos el complemento:

x & y = 0

Esto es cierto si y solo si cada bit activado de y yace fuera de x, es decir, y es una submáscara de ~x.

Como solo consideramos los $B$ bits más bajos:

~x = FULL_MASK ^ x

Así,

Número de y con x & y = 0 = dp[FULL_MASK ^ x]

Por lo tanto,

Número de y con x & y != 0 = n - dp[FULL_MASK ^ x]

Implementación

Complejidad temporal: $\mathcal{O}(B \cdot 2^{B} + N)$ , donde $B$ es el número de bits de la máscara.

C++


#include <bits/stdc++.h>
using namespace std;
 
constexpr int B = 20;
constexpr int FULL_MASK = (1 << B) - 1;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n;
	cin >> n;
 
	vector<int> a(n);
	for (int &x : a) cin >> x;
 
	vector<int> dp(1 << B), kp(1 << B);
 
	for (int x : a) dp[x]++, kp[x]++;
 
	for (int i = 0; i < B; ++i) {
		for (int mask = 0; mask < (1 << B); ++mask) {
			if (mask & (1 << i)) dp[mask] += dp[mask ^ (1 << i)];
			else kp[mask] += kp[mask ^ (1 << i)];
		}
	}
 
	for (int x : a)
		cout << dp[x] << ' ' << kp[x] << ' ' << n - dp[FULL_MASK ^ x] << '\n';
 
	return 0;
}