Я хочу сгенерировать n-й член последовательности 1,3,8,22,60, 164 в порядке (1) или порядке (nlogn)

Эта последовательность удовлетворяет условию a (n + 2) = 2 a (n + 1) + 2 a (n).

а также (n) = [(1 + sqrt (3)) ^ (n + 2) – (1-sqrt (3)) ^ (n + 2)] / (4sqrt (3)).

Я использую C ++ для меня n может варьироваться от 1 до 10 ^ 9. Мне нужны ответы modulo (10 ^ 9) +7 Но скорость здесь очень важна

Мой код с формулой 1 медленный для чисел> 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; } 

Я хочу более быстрый метод. Как я могу вычислить n-й член, используя вторую формулу. Есть ли какой-либо трюк для вычисления модулярных степеней десятичных знаков очень быстро? Есть ли у вас предложения по ускорению генерации этой последовательности?

Пожалуйста помоги

2 Solutions collect form web for “Я хочу сгенерировать n-й член последовательности 1,3,8,22,60, 164 в порядке (1) или порядке (nlogn)”

Вы можете рассчитать значения последовательностей с линейным рекуррентным соотношением в шагах O (log n) с использованием матричного метода. В этом случае matrix рекуррентности

 2 2 1 0 

Затем n член последовательности получается путем умножения n степени этой матрицы на два начальных значения.

Повторение немедленно переводит

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

таким образом

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

В этом случае начальные условия дают: x_1 = 1, x_2 = 3 приводят к x_0 = 0.5 , нецелое значение, поэтому вычисление должно быть скорее

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

Чтобы получить значение по модулю некоторого числа, вычислите мощность матрицы по модулю этого числа.

Я не хочу испортить удовольствие от изучения алгоритмических головоломок, поэтому я просто дам вам начальный намек: у вас есть в основном последовательность Фибоначчи с несколькими запутывающими элементами.

Давайте будем гением компьютера.