Xor Pyramid

Explicación

Simular el proceso, de forma similar al triángulo de Pascal , no es eficiente, porque $n$ es demasiado grande. Una buena práctica al tratar con problemas de este tipo es analizar cómo afecta cada valor individual a la respuesta. Teniendo en cuenta que el xor es su propio inverso, un valor $x$ xoreado consigo mismo un número par de veces da $0$ , cancelándose; por otro lado, el valor $x$ xoreado consigo mismo un número impar de veces simplemente da $x$ . En consecuencia, podemos cambiar el foco a hallar, para cada valor de la base, la cantidad de veces que afectará al valor de arriba.

Veamos cómo los valores de la base modifican el resultado final.

pyramid

Como se ve, el valor $B$ no aparece en el resultado final, así que se puede ignorar. Además, los valores de la fila de abajo en el triángulo de Pascal de altura cinco son $1,4,6,4,1$ . Podemos pensar estos valores como la cantidad de ocurrencias de cada valor de la fila de abajo. En la imagen de arriba, el valor $A$ se xoreará una vez en el resultado, mientras que el valor $B$ se xoreará cuatro veces en el resultado. Por lo tanto, la paridad de la frecuencia nos dice que el valor $A$ contribuye al resultado, mientras que el valor $B$ se cancela a sí mismo.

Como solo nos interesa la paridad del coeficiente binomial, no hace falta calcular su valor real. Podemos simplemente revisar la paridad contando la potencia de dos en $\binom{n}{k}=\frac{n!}{k! \cdot (n-k)!}$ . Con esto en mente, precomputamos $\texttt{pref}_i=p$ donde $p$ es la potencia de dos en la factorización de $i!$ . Por lo tanto, el coeficiente binomial es impar si: $\texttt{pref}_n-\texttt{pref}_k-\texttt{pref}_{n-k}=0$ .

Implementación

Complejidad temporal: $\mathcal{O}(N)$

C++JavaPython


#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	int n;
	cin >> n;
	vector<int> pref(n + 1);
	for (int i = 2; i <= n; i++) {
		int num = i;
		while (num % 2 == 0) {
			pref[i]++;
			num /= 2;
		}
		pref[i] += pref[i - 1];
	}
 
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		if (pref[n - 1] - pref[i] - pref[n - i - 1] == 0) { ans ^= num; }
	}
 
	cout << ans << endl;
}


import java.io.*;
import java.util.*;
 
public class XorPyramid {
	public static void main(String[] args) throws IOException {
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(f.readLine());
 
		int n = Integer.parseInt(st.nextToken());
 
		// Precomputar las potencias de 2 en la factorización de i!
		int[] pref = new int[n + 1];
		for (int i = 2; i <= n; i++) {
			int num = i;
			while (num % 2 == 0) {
				pref[i]++;
				num /= 2;
			}
			pref[i] += pref[i - 1];
		}
 
		int ans = 0;
		st = new StringTokenizer(f.readLine());
		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(st.nextToken());
 
			/*
			 * Determinar si el i-ésimo coeficiente binomial en
			 * el triángulo de Pascal es impar determinando la cantidad de
			 * 2s en la factorización de n choose k.
			 */
			if (pref[n - 1] - pref[i] - pref[n - i - 1] == 0) {
				/*
				 * Si no hay 2s, entonces el i-ésimo coeficiente es impar.
				 * Esto significa que num aparecerá en nuestra respuesta,
				 * así que lo xoreamos a nuestra respuesta.
				 */
				ans ^= num;
			}
		}
 
		out.println(ans);
		out.close();
	}
}


n = int(input().strip())
 
# Inicializar el arreglo de prefijos
pref = [0] * (n + 1)
 
# Calcular la cantidad de ceros a la derecha en cada número hasta n
for i in range(2, n + 1):
	num = i
	while num % 2 == 0:
		pref[i] += 1
		num //= 2
	pref[i] += pref[i - 1]
 
ans = 0
 
data = list(map(int, input().strip().split()))
 
# Calcular el resultado usando XOR
for i in range(n):
	num = data[i]
	if pref[n - 1] - pref[i] - pref[n - i - 1] == 0:
		ans ^= num
 
print(ans)