xortransform

Análisis oficial (en rumano) 

Explicación

Tras ejecutar la solución de fuerza bruta, se puede observar que el período de cómo se ve la matriz es la menor potencia de dos que es mayor que $n$ y que $m$.

Además, podemos reducir el problema a hallar la xor-suma de los elementos en posiciones tales que el número de caminos de $(0, 0)$ a $(i, j)$ en $k$ pasos es impar, donde $k$ es el número de transformaciones hechas.

Esto es igual a $C(k, i) \cdot C(k, j)$, donde $C(n, k)$ es $n$ sobre $k$. Además, si $C(n, k)$ es impar, entonces $n \& k = k$ (esto también se puede observar por fuerza bruta).

Además, si $C(n, i)$ y $C(n, j)$ son impares, entonces $C(n, i|j)$ también es impar, así que podemos reducir el problema a SOS DP, donde $SOS[i]$ = xor-suma de los elementos que están en posiciones incluidas por $i$.

Para cada bit del período, $SOS[i] = SOS[i - 2^{position}] \oplus SOS[i]$, si $i$ tiene el bit en esa posición igual a $1$.

Para otros enfoques, también se pueden ver las soluciones de usuarios en Infoarena ; solo hay que pulsar el popup que aparece al hacer clic por primera vez en una solución. Hay que tener en cuenta que la versión usada es ligeramente distinta de la versión real, ya que este problema se dio como problema interactivo e Infoarena no podía soportar problemas interactivos en ese momento.

Implementación para la versión de Infoarena

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

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ifstream f("xortransform.in");
	int n, m, q;
	f >> n >> m >> q;
	vector<int> sos(n * m * 2 + 1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int nr;
			f >> nr;
			sos[i | j] ^= nr;
		}
	}
 
	int mx = 1;
	int stp = 1;
	while (mx < n || mx < m) {
		mx <<= 1;
		stp++;
	}
	for (int i = 0; i < stp; i++) {
		for (int j = 0; j < mx; j++) {
			if (j & (1 << i)) { sos[j] ^= sos[j - (1 << i)]; }
		}
	}
 
	int prev_ans = 0;
	ofstream g("xortransform.out");
	for (int i = 0; i < q; i++) {
		int nr;
		f >> nr;
		nr ^= prev_ans;
		nr &= (mx - 1);
		prev_ans = sos[nr];
		g << prev_ans << '\n';
	}
}