enésimo término de la serie

tenemos que encontrar el enésimo término de esta serie http://oeis.org/A028859 enésimo término de la serie

n < = 1000000000

respuesta debe ser modulo 1000000007

he escrito el código, pero límite de tiempo excede cuando na es un gran número.

#include<iostream> 
using namespace std 

int main() 
{ 
    long long int n; 
    cin>>n; 

    long long int a,b,c; 
    a=1; 
    b=3; 

    int i; 
    for(i=3;i<=n;i++) 
    { 
     c=(2ll*(a+b))%1000000007; 
     a=b; 
     b=c; 
    } 

    cout<<c; 
}

Fuente

2012-07-01 user1484638

Cualquier posibilidad de que podría pegar en un ejemplo de código más limpio que éste, mediante sangrado adecuado y evitar el excesivo espacio en blanco? –

¿Qué tiene esto que ver con la programación dinámica? – Mathias

Pruebe la versión recursiva de este algoritmo y comprenderá cómo se trata de un algoritmo de programación dinámica. Básicamente, almacenamos los valores calculados de n-1 y n-2. Digamos que es una versión básica de DP. –

La técnica estándar para resolver este tipo de problema es reescribirla como una multiplicación de matriz y luego usar exponentiation by squaring para calcular eficientemente las potencias de la matriz.

En este caso:

a(n+2) = 2 a(n+1) + 2 a(n) 
a(n+1) = a(n+1) 

(a(n+2)) = (2 2) * (a(n+1)) 
(a(n+1)) (1 0) (a(n) )

Así que si definimos la matriz A = [2,2; 1,0], entonces se puede calcular el enésimo término por

[1,0] * A^(n-2) * [3;1]

Todas estas operaciones se pueden hacer modulo 1000000007 tanto, no requiere la biblioteca número grande.

Requiere O (log (n)) 2 * 2 multiplicaciones de matriz para calcular A^N, por lo general este método es O (log (n)), mientras que su método original fue O (n).

EDITAR

Here es una buena explicación y una aplicación C++ de este método.

Fuente

2012-07-01 21:19:28

[Aquí] (http://stackoverflow.com/a/26281100/461597) He respondido una pregunta similar, pero también he utilizado el Teorema de Euler. 1000 ... 07 es un número primo, por lo que no tiene que calcular A^N, pero A^(N% (p-1)) es suficiente. De esta forma, el método se convierte en O (1) (o O (p) pero p es constante) en lugar de O (log (n)). – Unapiedra

Cuando long long no es suficiente, es probable que desee utilizar una biblioteca bignum. Por ejemplo GNU MP.

Fuente

2012-07-01 20:56:58 iblue

pero tenemos que dar respuesta al módulo 1000000007 – user1484638

No solo es ** long long int ** suficiente, pero creo que ** unsigned long int ** también es suficiente ya que el valor máximo posible es 4 * 10000007 <4294967295. –

bien ... puede sugerir un enfoque para este problema – user1484638

Respuesta

Cuestiones relacionadas