Quiero generar el enésimo término de la secuencia 1,3,8,22,60, 164 en el orden (1) o el orden de (nlogn)

Esta secuencia satisface a (n + 2) = 2 a (n + 1) + 2 a (n).

y también a (n) = [(1 + sqrt (3)) ^ (n + 2) – (1-sqrt (3)) ^ (n + 2)] / (4sqrt (3)).

Estoy usando C ++ para mí n puede variar de 1 a 10 ^ 9. Necesito las respuestas módulo (10 ^ 9) +7 Pero la velocidad aquí es muy importante

Mi código con formula1 es lento para números> 10 ^ 7

#include  #define big unsigned long long int #include int ans[100000001]={0}; big m =1000000007; using namespace std; int main() { //cout << "Hello world!" <>t; big a,b,c; a=1; b=3; c=8; ans[0]=0; ans[1]=1; ans[2]=3; ans[3]=8; for(big i=3;i<=100000000;i++) { ans[i]=(((((ans[i-2])+(ans[i-1])))%m)<>n; // if(n==1){ // cout<<1<<endl;f++;} // if(n==2){ // cout<<3<<endl; // f++; // } // if(!f){ // a=1; // b=3; // c=8; // for(big i=3;i<=n;i++) // { // c=(((((a)+(b // )))%m)<<1)%m; // a=b%m ; // b=c%m; // } // cout<<ans[n]<>n; if(n<=100000000) cout<<ans[n]<<endl; else cout<<rand()%m; } return 0; } 

Quiero un método más rápido. ¿Cómo puedo calcular el enésimo término usando la segunda fórmula? ¿Hay algún truco para calcular las potencias modulares de los decimales muy rápidamente? ¿Tiene alguna sugerencia para una generación más rápida de esta secuencia?

Por favor ayuda

Puede calcular los valores de las secuencias con una relación de recidiva lineal en los pasos O (log n) usando el método de la matriz. En este caso, la matriz de recurrencia es

 2 2 1 0 

El enésimo término de la secuencia se obtiene multiplicando la enésima potencia de esa matriz con los dos valores iniciales.

La recurrencia se traduce de inmediato a

 |x_n | |2 2| |x_(n-1)| |x_(n-1)| = |1 0| * |x_(n-2)| 

así

 |x_(n+1)| |2 2|^n |x_1| |x_n | = |1 0| * |x_0|. 

En este caso, las condiciones iniciales dan, x_1 = 1, x_2 = 3 llevan a x_0 = 0.5 , un valor no entero, por lo tanto, el cálculo debería ser más bien

 |x_(n+1)| |2 2|^(n-1) |x_2| |x_n | = |1 0| * |x_1|. 

Para obtener el módulo de valor de algún número, calcule el poder del módulo de la matriz de ese número.

No quiero echar a perder la diversión de explorar la solución de acertijos algorítmicos, así que les daré una pista inicial: lo que tienen allí es básicamente una secuencia de Fibonacci con algunos elementos confusos.