Matrix Exponentiation (Theory Parte 1)


  • administrators

    Antes que nada aclarar que no se trata de aprender a multiplicar y exponenciar matrices rápidamente. Acá se hablará de una técnica para resolver problemas de un determinado tipo.

    Primero aprendamos algo básico resolviendo un problema simple que nos sera muy util al completar el tema:

    Problema 1 - Hallar el resultado de la potencia de un numero

    Si hablamos de una potencia de 2 que logre entrar en un entero o en un entero de 64 bits el problema es muy fácil ya que solo basta con utilizar un ciclo que vaya multiplicando por 2 nuestro multiplicador en cada iteración.

    int mul = 1;
    for (int i = 0 ; i < n ; i++) {
        mul *= 2;
    }
    cout << mul << endl;
    

    Que sucede si nuestro propósito es encontrar el n-esimo valor de la formula $X^N$ pero en este caso $N$ puede ser $10^{18}$. Si utilizamos un simple FOR daria Time Limit Excedent. La respuesta al problema se encuentra utilizando "Exponentiation By Squaring" o "Exponenciación Binaria" un método matemático computacional para obtener potencias de números grandes rápidamente. El resultado de estas operaciones puede dar como resultado un número muy grande, por esto en la mayoría de los ejercicios de este tipo nos piden que se imprima el resultado modulo M (donde M es un entero por lo general primo, ej: 1000000007 ).

    A continuación se encuentra una función en C++ para obtener el resultado de la formula $X^N$ modulo $M$ ($M = 1007$ para $N > 0$) utilizando Exponenciación Binaria.

    long long binaryExp (long long X, long long N) {
        long long mul = 1;
        long long expo = X;
        long long M = 1007;
        for (int i = 0 ; i < 62 ; i++) {
            if (N & (1LL << i))
                mul = (mul * expo) % M;
            expo = (expo * expo) % M;
        }
        return mul;
    }
    

    Este algoritmo esta basado en la siguiente observación.
    $$\begin{equation*}
    X^N=
    \begin{cases}
    X*(X^2)^{\frac{N-1}{2}}, & \text{si}\ N \text{ es impar}\ \\
    (X^2)^{\frac{N}{2}}, & \text{si}\ N \text{ es par}
    \end{cases}
    \end{equation*}$$
    Para ver la igualdad de la fórmula con el código sugiero realizar una prueba en papel y detectar la similitud en las listas de números resultantes.

    Ahora que entendemos mejor Exponenciación Binaria ya podemos comenzar a resolver problemas donde la recurrencia esta ligada a la iteración inmediatamente inferior, veamos un ejemplo.

    Problema A: OBI Hack

    Descripción

    Los alumnos de la OBI lograron Hackear el sistema de calificación, este Hack puede automáticamente dar la nota al alumno que ingrese, de hasta 3 veces la nota que registro el ultimo niño.

    Si todos los niños usan el Hack excepto el primero, que nota tendría el $n-esimo$ niño si el primero saco una nota de “P” ?

    Imprime el numero resultante, como el resultado puede ser muy grande necesitamos la respuesta modulo 10007.

    Solución

    La recurrencia del problema en este caso es simple análisis del enunciado, esta dada con la formula:

    $$\begin{equation*}
    Solu_i=
    \begin{cases}
    P, & \text{si}\ N \text{ es 1}\ \\
    Solu_{i-1} * 3, & \text{si}\ N \text{ es mayor que 1}
    \end{cases}
    \end{equation*}$$

    Esta formula se puede simplificar mas pero es mejor aprender a verla desde el punto de vista actual. Que estamos haciendo en la anterior formula ? Veamos para $N = 4$ como se descompone la formula si sabemos que "$Solucion_4$ es igual a $Solucion_3$ por 3 y Solucion_3 a su vez es $Solucion_2$ por 3, y $Solucion_2$ es $Solucion_1$ * 3 y $Solucion_1$ es igual a P".

    $$\begin{align*}
    Solu_4 & = 3 * Solu_3\\
    Solu_4 & = 3 * (3 * Solu_2)\\
    Solu_4 & = 3 * (3 * (3 * Solu_1))\\
    Solu_4 & = 3 * 3 * 3 * P\\
    Solu_4 & = 3^3 * P\\
    \end{align*}$$

    Ahora todo tiene sentido, para resolver este problema solo necesitamos obtener la potencia $n-1$ de $3$ y multiplicando por $P$ lograremos encontrar el valor de la solución, nunca olvidando de poner el modulo en las operaciones necesarias para dar un resultado, tenemos el siguiente código de solución al problema donde se muestra una Implementación mas avanzada de la Exponenciación Binaria.

    const int MOD = 10007;
    
    long long getExpo (long long X, long long power) {
        long long res = 1;
        while (power > 0) {
            if (power & 1) res = (res * X) % MOD;
            X = (X * X) % MOD;
            power >>= 1; // power = power / 2;
        }
        return res;
    }
    
    int main() {
        int n, P;
        cin >> n >> P;
        if(n == 1)
            cout << P << endl;
        else
            cout << (getExpo(3, n-1) * P) % MOD << endl;
    }
    

    Conclusión

    Las diferentes recurrencias que se encuentran en problemas tipo ICPC, CodeJam, HackerCup, etc. Por lo general están ligadas a fórmulas que se pueden expresar en matrices.

    Las recursiones que necesitan simplemente del valor anterior a la respuesta actual se pueden obtener como vimos con el exponente n-esimo multiplicado por el valor inicial. Pero que pasa si la recursión contiene dos o mas valores anteriores ? o si contiene constantes ? Eso y mas veremos en la siguiente sección (Parte 2).