Я решаю проблему 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)
и ничего не возвращает. Пожалуйста, помогите мне понять проблему здесь и как с ней бороться. Любые другие предложения также будут оценены.
Посмотрите на математику. Если бы одно из ваших дополнений заняло одну наносекунду (что очень оптимистично), а n
было бы 10 ^ 18, ваша программа работала бы почти 32 года. Это говорит о том, что должен быть более быстрый метод. (Кроме того, для вашего массива потребуется восемь миллионов гигабайт. Вам нужно только сохранить два последних числа Фибоначчи, чтобы вычислить следующее.)
Компиляторы C++ не гарантируют поддержку VLA. Итак, это unsigned long long int seq[n];
вызывает Неопределенное Поведение. Пожалуйста, убедитесь, что это не причина
Ваш текст говорит по модулю 7, а ваш код вычисляет по модулю 1000000007. Какое из них является ожидаемым значением?
@SergeBallesta 1000000007. Это обычное число в алгоритмических задачах для предотвращения переполнения целых чисел.
@molbdnilo Правильно, ключевое наблюдение, если кто-то действительно хочет решить эту проблему, состоит в том, чтобы выяснить, как вычислить сумму без сложения всех членов (поскольку это займет годы), а ЗАТЕМ переписать эту формулу, используя связанные ответы.
При модульном добавлении вам нужно применить свой мод к каждому добавляемому значению.
Например, (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]
приведет к переполнению.
Подробнее о модульной арифметике читайте здесь.
Однако у меня есть сомнения, что seq[i - 1] = (seq[i-2] + seq[i-3]) % mod. Итак, на seq[i - 1] уже есть мод, так зачем же нужно 2 мода?
Вы правы, я не уловил этого. Я думаю, что добавление строки seq[i] %= mod
в ваш цикл после добавления должно помочь, без необходимости двух дополнительных модов.
В этой проблеме
F[i] -> i-е число Фибоначчи. MOD = 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;
}
можете ли вы объяснить математику за этим? какие-либо дополнительные статьи для чтения или видео для просмотра
Я думаю, что проблема с этим кодом заключается в том, что вы создаете массив 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;
}
Ни один из ваших ответов не является правильным
Как вы пришли к такому выводу?
Короткий поиск показывает Проверить, является ли число числом Фибоначчи с большим количеством ответов, касающихся больших чисел, превышающих 64-битные.