Как найти суммы Фибоначчи огромных чисел? [дубликат]

Question

Я решаю задачу CSES, в которой мне нужно найти сумму первых n чисел Фибоначчи. Код:

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

Проблема указывает, что значение n может достигать 10 ^ 18, и поэтому я использовал unsigned long long int для инициализации n. Задача также требует дать ответ по модулю 7. Код работает нормально для значений от n до 4 цифр, но прерывается, когда значение n поднимается до верхнего предела 10 ^ 18, выдает (0xC00000FD)ошибку и ничего не возвращает. Пожалуйста, помогите мне понять суть проблемы и способы ее решения. Любые другие предложения также будут оценены.

Answer 1

В этой проблеме

F [i] -> i-е число Фибоначчи. МОД = 1e9 + 7. n <1e18

F [n]% MOD =?

F [n] = F [n-1] + F [n-2], если вы вычислите это с помощью цикла, вы получите TL

так вы можете оптимизировать это решение

теперь вы вычисляете F [n] с рекурсией

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]

вот мое решение

#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

При модульном добавлении вам необходимо применить свой мод к каждому добавляемому значению.

Например, (a + b)% c = (a% c + b% c)% c.

Это означает в вашем коде:

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

В противном случае добавление seq[i - 1]и seq[i - 2]приведет к переполнению.

Подробнее о модульной арифметике здесь .

Answer 3

Я думаю, что проблема с этим кодом в том, что вы создаете массив seq[n]размера n, что может привести к ошибкам SEGFAULTв Linux и STATUS_STACK_OVERFLOW (0xc00000fd)Windows для больших чисел, что относится к исчерпанию стека.

Ниже я привожу улучшенную версию вашего алгоритма, в которой используется фиксированный размер памяти, а для сложения по модулю я использую sum_by_moduloфункцию, чтобы избежать переполнения при (a + b) % mработе, принцип которой описан здесь .

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