math - cómo calcular 2 ^ n módulo 1000000007, n=10 ^ 9

matrix eigenvector

Question

¿Cuál es el método más rápido para calcular esto? Vi a algunas personas usar matrices y cuando busqué en Internet, hablaron sobre valores propios y vectores propios (no tengo idea de esto) ... hubo una pregunta que se redujo a un recursivo la ecuación f (n) = (2 * f (n-1)) + 2, y f (1) = 1, n podría ser hasta 10 ^ 9 ... ya intenté usar DP, almacenando hasta 1000000 valores y usando el método de exponenciación rápida común, todo se agotó, generalmente es débil en estas preguntas de módulo, que requieren cálculos de gran tamaño

Answer 1

f(n) = (2*f(n-1)) + 2 with f(1)=1

es equivalente a

(f(n)+2) = 2 * (f(n-1)+2)
         = ...
         = 2^(n-1) * (f(1)+2) = 3 * 2^(n-1)

para que finalmente

f(n) = 3 * 2^(n-1) - 2

donde puede aplicar métodos rápidos de potencia modular.

Answer 2

Exponenciación modular por el método de cuadrado y multiplicación:

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e%2 == 1
            x, e := (x*b)%m, e-1
        else b, e := (b*b)%m, e//2
    return x