I numeri di figonacci

Aiuto
1

Ciao a tutti ragazzi,
è da poco che ho cominciato a risolvere problemi e mi ritrovo bloccato su questo https://training.olinfo.it/#/task/figonacci/statement.
Riesco a completare le prime due subtask con questa soluzione rudimentale:

#include <bits/stdc++.h>
#define MAXN 10000
using namespace std;
vector<long long> figonacci;
int somma (int N, vector<int> V) {
	int s = 0;
	for (int i = 0; i <= N; i++)
		s = V[N]-V[N - i] + s;
	return s;
}
int enumera(int N, int M) {
	int a[] = {-1, 0};
	figonacci.assign(a, a + 2);
	for (int i = 2; i <= 100; i++) {
		figonacci.push_back(somma(i-1, figonacci));
	}
	for (int i = 0; i <= 100; i++)
		cout<<figonacci[i]<<"\n";
    return figonacci[N] % M;
}

Quando vado a provare a farlo con N <= 100 la soluzione mi va in overflow (?) e non ho idea di come fare.
Ringrazio chiunque cerchi di darmi una mano

2

Ciao! Evitare l’overflow è molto semplice, è anche scritto nel testo del problema tra le note:
"L’operazione di modulo, inoltre, ha le seguenti proprietà (molto utili per evitare integer overflow quandosi vogliono calcolare numeri molto grandi):

  • (A+B) modM= (AmodM+BmodM) modM
  • (A·B) modM= (AmodM·BmodM) modM

Significa che puoi calcolare il modulo per ogni operazione che fai e comunque ottenere il risultato corretto.
Per velocizzare il tempo basta applicare la proprietà commutativa della somma:
\sum_{i=0}^{n-1}(G_n-G_i)=\sum_{i=0}^{n-1}G_n-\sum_{i=0}^{n-1}G_i=nG_n-\sum_{i=0}^{n-1}G_i.
Quindi basta salvarsi la somma dei precedenti (fino a i-1) e toglierla da i volte l’ultimo numero di Figonacci trovato per ottenere l’i+1esimo (poi regolati tu con gli indici).

1 Mi Piace