Büyük sayıların fibonacci toplamları nasıl bulunur? [çiftleme]
İlk 'n' Fibonacci sayılarının toplamını bulmam gereken bir CSES problemini çözüyorum. Kod:
#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];
}
Sorun n'nin değerinin 10 ^ 18'e kadar çıkabileceğini ve bu nedenle unsigned long long int
n'yi başlatmak için kullandım . Problem aynı zamanda modulo 7 cevabını vermeyi de öğretir. Kod, 4 haneye kadar n değerleri için iyi çalışıyor, ancak n'nin değeri 10 ^ 18 üst tavanına yükseldiğinde kırılıyor, (0xC00000FD)
hata veriyor ve hiçbir şey döndürmüyor. Lütfen buradaki sorunu ve bununla nasıl başa çıkılacağını anlamama yardım edin. Başka herhangi bir öneri de memnuniyetle karşılanacaktır.
Yanıtlar
Bu problemde
F [i] -> i. Fibonacci sayısı. MOD = 1e9 + 7. n <1e18
F [n]% MOD =?
F [n] = F [n-1] + F [n-2] bunu döngü ile hesaplarsanız TL alırsınız
bu çözümü optimize etmenin yolu
şimdi özyineleme ile F [n] 'yi hesaplar
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]
işte benim çözümüm
#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;
}
Modüler ekleme yaparken, modunuzu eklediğiniz her değere uygulamanız gerekir.
Örneğin, (a + b)% c = (a% c + b% c)% c.
Bu, kodunuzda şu anlama gelir:
seq[i] = (seq[i - 1] % mod + seq[i - 2] % mod) % mod;
Aksi takdirde, eklenmesi seq[i - 1]
ve seq[i - 2]
bir taşma ile sonuçlanacaktır.
Modüler aritmetik hakkında daha fazlasını buradan okuyun .
Bu kod ile sorun bir dizi yaratmak olduğunu düşünüyorum seq[n]
büyüklükte n
bir yol açabilir, SEGFAULT
Linux ve STATUS_STACK_OVERFLOW (0xc00000fd)
yorgunluktan yığını anlamına gelir büyük sayılar için Windows üzerinde.
Aşağıda, algoritmanızın sabit bir bellek boyutu kullanan geliştirilmiş bir versiyonunu veriyorum ve modulo eklemek için, bu sum_by_modulo
işlevi, (a + b) % m
çalışma sırasında taşmayı önlemek için kullanıyorum , prensibi burada açıklanmıştır .
#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;
}