Làm thế nào để tìm tổng fibonacci của những con số khổng lồ? [bản sao]

Question

Tôi đang giải một bài toán CSES, trong đó tôi phải tìm tổng các số Fibonacci 'n' đầu tiên. Mật mã:

#pragma GCC optimize("Ofast")
#include <iostream>
 
using namespace std;
 
int main()
{
    unsigned long long int n;
    scanf("%llu", &n);
    unsigned long long int seq[n];
    seq[0] = 0;
    seq[1] = 1;
    unsigned long long int mod = 1000000000 + 7;
    for (unsigned long long int i = 2; i < n + 1; i++) {
        seq[i] = (seq[i - 1] + seq[i - 2]) % mod;
    }
    cout << seq[n];
}

Bài toán chỉ định rằng giá trị của n có thể nhận tối đa 10 ^ 18 và do đó tôi đã sử dụng unsigned long long int để khởi tạo n. Bài toán cũng hướng dẫn đưa ra đáp án modulo 7. Mã đang hoạt động tốt đối với các giá trị của n có tối đa 4 chữ số nhưng bị hỏng khi giá trị của n tăng lên mức trần trên là 10 ^ 18. Nó (0xC00000FD)báo lỗi và không trả về bất kỳ thứ gì. Xin vui lòng giúp tôi hiểu vấn đề ở đây và làm thế nào để đối phó với nó. Bất kỳ đề xuất khác cũng sẽ được đánh giá cao.

Answer 1

Trong vấn đề này

F [i] -> số Fibonacci thứ i. MOD = 1e9 + 7. n <1e18

F [n]% MOD =?

F [n] = F [n-1] + F [n-2] nếu bạn tính toán điều này với vòng lặp, bạn sẽ nhận được TL

đó là cách bạn có thể tối ưu hóa giải pháp này

bây giờ bạn tính F [n] với đệ quy

F [2 * n] = - F [n] * F [n] + 2 * F [n] * F [n + 1]

F [2 * n + 1] = F [n] * F [n] + F [n + 1] * F [n + 1]

đây là giải pháp của tôi

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD = 1e9+7;
void fib(ll n ,ll &a , ll &b){
    if(n == 0){
        a = 0;
        b = 1;
        return;
    }
    ll x, y;
    if(n%2==1){
        fib(n-1 ,x,y);
        a = y;
        b = (x+y)%MOD;
        return;
    }
    fib(n/2 , x , y);
    a = (x*(2*y +MOD -x)%MOD)%MOD;
    b = ((x*x)%MOD+(y*y)%MOD)%MOD;
    return;
}
int main(){
    ll N , a, b;
    cin >> N;
    fib(N , a, b);
    cout << a;
}

Answer 2

Khi thực hiện thêm mô-đun, bạn cần áp dụng mô-đun của mình cho từng giá trị bạn đang thêm.

Ví dụ, (a + b)% c = (a% c + b% c)% c.

Điều đó có nghĩa là trong mã của bạn:

seq[i] = (seq[i - 1] % mod + seq[i - 2] % mod) % mod;

Nếu không, việc thêm seq[i - 1]và seq[i - 2]sẽ dẫn đến tràn.

Đọc thêm về số học mô-đun tại đây .

Answer 3

Tôi nghĩ rằng vấn đề với mã này là bạn đang tạo một mảng seq[n]có kích thước n, có thể dẫn đến một số lượng lớn SEGFAULTtrên Linux và STATUS_STACK_OVERFLOW (0xc00000fd)trên Windows, điều này có nghĩa là cạn kiệt ngăn xếp.

Dưới đây, tôi đưa ra một phiên bản cải tiến của thuật toán của bạn, sử dụng kích thước bộ nhớ cố định và để bổ sung mô-đun, tôi sử dụng sum_by_modulohàm, để tránh tràn khi (a + b) % mhoạt động, nguyên tắc của nó được mô tả ở đây .

#pragma GCC optimize("Ofast")
#include <iostream>
 
typedef unsigned long long int ullong;

ullong sum_by_modulo(ullong a, ullong b, ullong m){
    ullong sum;
    a %= m;
    b %= m;
    ullong c = m - a;

    if (b==c)
        sum = 0;
    if (b<c)
        sum = a + b;
    if (b > c)
        sum = b-c;
    return sum;
}

int main()
{
    ullong n;
    ullong t1 = 0, t2 = 1, nextTerm = 0;
    ullong modulo = 1000000000 + 7;    

    std::cout << "Enter the number of term: ";
    std::cin >> n;

    for (ullong i = 1; i <= n; ++i)
    {
        if(i == 1)
            continue;
        if(i == 2)
            continue;
        nextTerm = sum_by_modulo(t1, t2, modulo);
        t1 = t2;
        t2 = nextTerm;
    }
    std::cout << nextTerm << " ";
    return 0;
}