мы должны найти n-й член этого ряда http://oeis.org/A028859
n<=1000000000
ответ должен быть по модулю 1000000007
я написал код, но срок превышается, когда n a является огромным числом.
#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;
}
Стандартный метод решения задач такого типа состоит в том, чтобы переписать ее как умножение матриц, а затем использовать возведение в степень путем возведения в квадрат для эффективного вычисления степени матрицы.
В таком случае:
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) )
Итак, если мы определим матрицу A=[2,2 ; 1,0], то вы можете вычислить n-й член с помощью
[1,0] * A^(n-2) * [3;1]
Все эти операции можно выполнять по модулю 1000000007, поэтому библиотека больших чисел не требуется.
Для вычисления A ^ N требуется O (log (n)) 2 * 2 матричных умножения, поэтому в целом этот метод равен O (log (n)), тогда как ваш исходный метод был O (n).
РЕДАКТИРОВАТЬ
Вот хорошее объяснение и реализация этого метода на C++ .
Когда long long недостаточно, вы, вероятно, захотите использовать библиотеку bignum. Например, GNU MP.
