膨大な数のフィボナッチ和を見つける方法は？[複製]
最初の「n」フィボナッチ数の合計を見つけなければならないCSES問題を解決しています。コード：
#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の答えを与えるように指示します。コードは4桁までのnの値に対しては正常に機能しますが、nの値が10 ^ 18の上限に達すると壊れ(0xC00000FD)ます。エラーが発生し、何も返されません。ここでの問題とその対処方法を理解するのを手伝ってください。他の提案もいただければ幸いです。
回答
この問題では
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;
}
モジュール式の追加を行うときは、追加する各値にmodを適用する必要があります。
たとえば、（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[n]、サイズの配列を作成していることだと思います。これは、LinuxおよびWindowsで多数n発生する可能性があり、スタックの枯渇を意味します。SEGFAULTSTATUS_STACK_OVERFLOW (0xc00000fd)
以下に、固定メモリサイズを使用するアルゴリズムの改良版を示します。モジュロ加算には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;
}