Primero, imagine que cada elemento de entrada es solo un bit (0 o 1). Luego, la operación de redondeo XOR es equivalente a tomar la matriz como un vector de bits y multiplicarla por una matriz donde la primera fila es 11000 … 001 y cada fila subsiguiente se obtiene girando a la derecha un bit. Por ejemplo, para [matemáticas] N = 6 [/ matemáticas], la matriz es:
110001
111000
011100
001110
000111
100011
Para aplicar las rondas XOR [math] K [/ math], podemos elevar esta matriz a la potencia de [math] K [/ math] y luego multiplicarla por el vector de entrada para obtener el resultado final.
- ¿Las funciones de JavaScript como map (), reduce () y filter () ya están optimizadas para recorrer la matriz?
- Si un hombre está limitado por el conocimiento, ¿podemos crear un algoritmo para sus elecciones y determinar su futuro?
- ¿Cuáles son los beneficios del árbol de búsqueda binario?
- ¿Alguien puede enviar el código para la búsqueda binaria en cadenas con clasificación en C ++?
- Cómo dividir una matriz en 2 nuevas variables de matriz y encontrar el promedio de ellas
Aunque [math] K [/ math] es grande, podemos usar el algoritmo de cuadrado y multiplicación para realizar la exponenciación usando solo [math] O (\ log K) [/ math] multiplicaciones de matriz individuales. Sin embargo, una sola matriz de multiplicación seguirá siendo lenta cuando [matemática] N = 500 [/ matemática]. Para acelerarlo, solo tenga en cuenta que cada vez que realizamos una multiplicación matricial, solo necesitamos calcular la primera fila del resultado; todas las demás filas se pueden completar simplemente girando hacia la derecha. Esto permite que la potencia [matemática] K [/ matemática] de la matriz se calcule solo en [matemática] O (N ^ 2 \ log K) [/ matemática] tiempo en lugar de [matemática] O (N ^ 3 \ log K) [/ math] time.
Resolver el problema para números de varios bits es fácil. Se toma la matriz final y, en lugar de multiplicarla por la matriz de entrada, es decir, al usar cada fila como plantilla para los bits que se deben agregar en el vector de la columna de entrada, se usa cada fila como plantilla para qué elementos XOR en el vector de columna de entrada.
