ennesima termine della serie di

dobbiamo trovare il termine ennesima di questa serie http://oeis.org/A028859 ennesima termine della serie di

n < = 1000000000

risposta dovrebbe essere MODULO 1000000007

ho scritto il codice, ma limite di tempo supera quando na è un numero enorme.

#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; 
}

fonte

2012-07-01 user1484638

Qualunque possibilità si potrebbe incollare in un campione di codice più pulito di questo, utilizzando una rientranza adeguata ed evitando lo spazio bianco eccessivo? –

Cosa c'entra questo con la programmazione dinamica? – Mathias

Prova la versione ricorsiva di questo algoritmo e capirai come questo è un algoritmo di programmazione dinamica. Fondamentalmente, memorizziamo i valori calcolati di n-1 e n-2. Diciamo, è una versione fondamentale di DP. –

La tecnica standard per risolvere questo tipo di problema è riscriverla come una moltiplicazione di matrice e quindi utilizzare exponentiation by squaring per calcolare in modo efficiente i poteri della matrice.

In questo 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) )

Quindi se definiamo la matrice A = [2,2; 1,0], allora si può calcolare l'n-esimo termine

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

Tutte queste operazioni possono essere eseguite modulo 1.000.000,007 mila così è richiesto nessun grande libreria di numero.

Richiede O (log (n)) moltiplicazioni di matrice 2 * 2 per calcolare A^N, quindi nel complesso questo metodo è O (log (n)), mentre il metodo originale era O (n).

EDIT

Here è una buona spiegazione e C++ attuazione di tale metodo.

fonte

2012-07-01 21:19:28

[qui] (http://stackoverflow.com)/a/26281100/461597) Ho risposto a una domanda simile, ma utilizzando anche il Teorema di Eulero. 1000 ... 07 è un numero primo, quindi non è necessario calcolare A^N ma A^(N% (p-1)) è sufficiente. In questo modo il metodo diventa O (1) (o O (p) ma p è costante) invece di O (log (n)). – Unapiedra

Quando long long non è abbastanza, probabilmente desidera utilizzare una libreria bignum. Ad esempio GNU MP.

fonte

2012-07-01 20:56:58 iblue

ma dobbiamo dare risposta modulo 1000000007 – user1484638

Non solo è ** lungo lungo int ** è sufficiente, ma credo che ** unsigned long int ** sia sufficiente poiché il valore massimo possibile è 4 * 10000007 <4294967295. –

ok..se suggerisci un approccio per questo problema – user1484638

ennesima termine della serie di

risposta

Problemi correlati