thứ n hạn của loạt

Question

chúng ta phải tìm ra thuật ngữ thứ n của loạt bài này http://oeis.org/A028859

n < = 1000000000

câu trả lời nên được modulo 1000000007

i đã viết mã nhưng lần vượt quá giới hạn khi na là số lượng lớn.

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

Answer 1

Kỹ thuật tiêu chuẩn để giải quyết loại sự cố này là viết lại nó dưới dạng phép nhân và sau đó sử dụng exponentiation by squaring để tính toán hiệu quả các quyền hạn của ma trận.

Trong trường hợp này:

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

Vì vậy, nếu chúng ta định nghĩa ma trận A = [2,2; 1,0], sau đó bạn có thể tính toán thuật ngữ thứ n bằng cách

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

Tất cả các thao tác này có thể được thực hiện modulo 1000000007 do đó không yêu cầu thư viện số lớn.

Nó yêu cầu phép nhân O (log (n)) 2 * 2 để tính A^N, vì vậy tổng thể phương pháp này là O (log (n)), trong khi phương thức ban đầu của bạn là O (n).

EDIT

Here là giải thích tốt và triển khai C++ của phương pháp này.

Answer 2

Khi không có đủ, bạn có thể muốn sử dụng thư viện bignum. Ví dụ: GNU MP.