# Numeri di Figonacci : Problema

**URL:** <https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395>\
**Category:** Aiuto\
**Created:** [8 Febbraio 2017, 6:14pm UTC](https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395 "2017-02-08T18:14:37Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![Guido99](https://forum.olinfo.it/user_avatar/forum.olinfo.it/guido99/32/381_2.png) [@Guido99](https://forum.olinfo.it/u/Guido99)\
**Post date:** [8 Febbraio 2017, 6:14pm UTC](https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395/1 "2017-02-08T18:14:37Z")

</div>

Questo codice risolve solamente le prime 2 subtask , la 3 completamente sbagliata e nella 4, gli ultimi quattro test vanno fuori tempo fino ad arrivare intorno a 1.984s,cosa mi consigliate di implementare/corregere?

```auto
 #include <iostream>
 #include <fstream>
 #include <string.h>
 #include <limits.h>
 #include <math.h>

using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");

int main(){

    int N,M;

	in>>N>>M;

	int f[N],max = 0;

    f[0] = -1;

    f[1] = 0;

    for(int i = 2; i<N+1; i++){		

			for(int j = i-2; j>=0; j--){
			
			    max = max + (f[i-1] - f[j]);

			}

			f[i] = max;

			max = 0;
	}

	out<<(f[N]%M + M)%M<<endl;
}

```

---

<div class="post-metadata">

**Author:** ![Gazzara](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/41988e/32.png) [@Gazzara](https://forum.olinfo.it/u/Gazzara)\
**Post date:** [8 Febbraio 2017, 8:08pm UTC](https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395/2 "2017-02-08T20:08:06Z")

</div>

Non ho fatto ancora il problema, ma è da implementare con la dinamica molto probabilmente, magari con la memoization.

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [8 Febbraio 2017, 8:11pm UTC](https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395/3 "2017-02-08T20:11:42Z")

</div>

La tua soluzione è una quadratica, che con N=10^6 va fuori tempo limite. L’obiettivo qui sarebbe una soluzione lineare, che però ha bisogno di una formula di ricorrenza “decente”, ovvero una formula di ricorrenza che si basi su un numero fisso di termini precedenti e non su tutti come nella descrizione data dal problema.  
Quello che ti serve è qualcosa sullo stile della ricorsione di fibonacci:

```
F(N) = F(N - 1) + F(N - 2)

```

In questo problema la formula è un po’ più complessa ma è possibile ricavarla con un minimo di attenzione.

Dario

_p.s.: Qualcuno sa se si può arrivare a un tempo logaritmico come con fibonacci?_

---

<div class="post-metadata">

**Author:** ![Guido99](https://forum.olinfo.it/user_avatar/forum.olinfo.it/guido99/32/381_2.png) [@Guido99](https://forum.olinfo.it/u/Guido99)\
**Post date:** [8 Febbraio 2017, 9:32pm UTC](https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395/4 "2017-02-08T21:32:03Z")

</div>

Ok grazie per le risposte ora vedrò come implementarlo

---

<div class="post-metadata">

**Author:** ![Guido99](https://forum.olinfo.it/user_avatar/forum.olinfo.it/guido99/32/381_2.png) [@Guido99](https://forum.olinfo.it/u/Guido99)\
**Post date:** [14 Aprile 2017, 3:41pm UTC](https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395/6 "2017-04-14T15:41:56Z")

</div>

Ciao dopo un pò di tempo sono tornato su questo problema e ho trovato questa formula che comunque mi fa rimanere su quei 30 pt.

```
        int f[N];
        f[0] = -1;
    	f[1] = 0;
    	f[2] = 1;
    	
        for(int i = 3; i<N+1; i++){
        	f[i] = (f[i-1] * (i-1))-(f[i-3] * (i-2));	    
    	}
      out<<(f[N]%M + M)%M<<endl;
```

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [14 Aprile 2017, 10:39pm UTC](https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395/7 "2017-04-14T22:39:19Z")

</div>

La formula non mi torna, come ci sei arrivato?  
Comunque quello che sicuramente non fai è applicare il modulo a ogni iterazione, cosa che ti fa sbagliare il risultato.

---

<div class="post-metadata">

**Author:** ![Guido99](https://forum.olinfo.it/user_avatar/forum.olinfo.it/guido99/32/381_2.png) [@Guido99](https://forum.olinfo.it/u/Guido99)\
**Post date:** [15 Aprile 2017, 8:45am UTC](https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395/8 "2017-04-15T08:45:22Z")

</div>

Ah grazie, mi è bastato aggiungere questa riga per ottenere 100 pt.

```
for(int i = 3; i<N+1; i++){
        	f[i] = (f[i-1] * (i-1))-(f[i-3] * (i-2));	    
            f[i] = (f[i] % M + M) % M;
    	}

```

Per quanto riguarda la formula mi sono scritto i valori della sequenza, e da li osservandola,(e provando dei calcoli) sono arrivato a questa formula

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [15 Aprile 2017, 8:57am UTC](https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395/9 "2017-04-15T08:57:34Z")

</div>

A questo punto, se può servire a qualcuno, questa è la formula che ho usato io:

f[i] = f[i - 1] + (i - 1) \* (f[i - 1] - f[i - 2])

---

<div class="post-metadata">

**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\
**Post date:** [29 Aprile 2017, 7:38pm UTC](https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395/10 "2017-04-29T19:38:51Z")

</div>

per il tempo logaritmico non saprei  
ragionando qua  
se  
f(n)=f(n-1)+f(n-2)  
f(n-1)=f(n-2)+f(n-3)  
allora  
f(n)=2\cdot f(n-2)+f(n-3)

se  
f(n-2)=f(n-3)+f(n-4)  
allora  
f(n)=2\cdot f(n-3)+2\cdot f(n-4)+f(n-3)=3\cdot f(n-3)+2\cdot f(n-4)

oserei una congettura tale che  
f(n)=f(i)\cdot f(n-i)+f(i-1)\cdot f(n-i-1)  
non saprei, sicuramente il quesito è interessante

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [29 Aprile 2017, 9:14pm UTC](https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395/11 "2017-04-29T21:14:38Z")

</div>

Vedo che stai lavorando con fibonacci, la soluzione in O(logN) funziona con l’esponenziazione rapida delle matrici.

Fib\_0 = 1  
Fib\_1 = 1

Definiamo s\_i = \begin{bmatrix} Fib\_i\\\ Fib\_{i - 1} \end{bmatrix} , s\_1 = \begin{bmatrix} 1\\\ 1 \end{bmatrix}

Possiamo calcolare gli elementi successivi come s\_i = s\_{i-1}\cdot \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} = s\_1 \cdot \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^i

Quindi per ottenere Fib\_i basta calcolare \begin{bmatrix} 1 & 1\\\ 1 & 0 \end{bmatrix}^i in O(\log{i}) e poi moltiplicare \begin{bmatrix} 1\\\ 1 \end{bmatrix} per il risultato.

Il problema è che questo tipo di definizione funziona solo per ricorrenze lineari, mentre tutte le ricorrenze per figonacci che ho trovato vogliono la moltiplicazione.

---

<div class="post-metadata">

**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\
**Post date:** [29 Aprile 2017, 10:23pm UTC](https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395/12 "2017-04-29T22:23:25Z")

</div>

Teoricamente hai ragione: se moltiplicare due matrici 2x2 ci costa O(1),  
calcolare \begin{bmatrix} 1 & 1 \cr 1 & 0 \cr \end{bmatrix}^i si fa in O(\log i).

Questa premessa cade però vista la rapida crescita dei numeri di fibonacci: quatttro normali interi a 32bit non riusciranno a contenere i valori degli elementi della matrice senza overflow.  
Raramente verrà chiesto di calcolare per intero Fib\_i con i\>30, quindi la soluzione lineare è accettabilissima.  
Da qui la questione: è possibile calcolare Fib\_i\mod{C} per un qualche C ragionevole -i.e. fitta in un intero 32 bit- in O(\log i), o comunque in complessità minore di O(i)?

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [30 Aprile 2017, 12:58pm UTC](https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395/13 "2017-04-30T12:58:07Z")

</div>

> [@lukecavabarrett](#):
>
> Da qui la questione: è possibile calcolare Fib\_i\mod{C} per un qualche C ragionevole -i.e. fitta in un intero 32 bit- in O(\log i), o comunque in complessità minore di O(i)?

Yup.  
Basta calcolare le matrici modulo C.

```
#include <cstdio>

constexpr int MOD = 1000000007;

int fib_linear(long long N)
{
	int f0 = 1, f1 = 1;
	for(long long i = 2; i < N; i++)
	{
		int tmp = f1;
		f1 = (f0 + f1) % MOD;
		f0 = tmp;
	}
	return f1;
}

void mat_mul(int mat[2][2], const int mul[2][2])
{
	int a = (mat[0][0] * 1LL * mul[0][0] + mat[0][1] * 1LL * mul[1][0]) % MOD;
	int b = (mat[0][0] * 1LL * mul[0][1] + mat[0][1] * 1LL * mul[1][1]) % MOD;
	int c = (mat[1][0] * 1LL * mul[0][0] + mat[1][1] * 1LL * mul[1][0]) % MOD;
	int d = (mat[1][0] * 1LL * mul[0][1] + mat[1][1] * 1LL * mul[1][1]) % MOD;
	mat[0][0] = a;
	mat[0][1] = b;
	mat[1][0] = c;
	mat[1][1] = d;
}

void fastexp(int mat[2][2], long long N)
{
	if(N <= 1) return;
	int mul[2][2] = {{1, 1}, {1, 0}};
	fastexp(mat, N / 2);
	mat_mul(mat, mat);
	if(N % 2) mat_mul(mat, mul);
}

int fib_logarithmic(long long N)
{
	int mat[2][2] = {{1, 1}, {1, 0}};
	fastexp(mat, N - 1);
	return mat[0][0];
}

int main()
{
	long long N;
	scanf("%lld", &N);
	printf("O(N) dp solution: %d\n", fib_linear(N));
	printf("O(logN) fastexp solution: %d\n", fib_logarithmic(N));
}

```

Ho provato la velocità di questo codice, per N = 2\cdot10^9 il calcolo lineare prende ~13s, quello logaritmico ~0s. Ho anche provato N meno ragionevoli (N = LLONG\_MAX) e comunque non sono riuscito a ottenere tempi superiori a ~0s.

In questo codice ho usato una definizione leggermente diversa di Fib\_i per evitare alla fine la moltiplicazione per \begin{bmatrix} 1\\ 1 \end{bmatrix}:

\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^i = \begin{bmatrix} Fib\_{i + 1} & Fib\_i\\ Fib\_i & Fib\_{i - 1} \end{bmatrix}

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [30 Aprile 2017, 1:57pm UTC](https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395/14 "2017-04-30T13:57:59Z")

</div>

Ho trovato un altro algoritmo in O(\log{N}\log{\log{N}}) per Fibonacci, rigorosamente senza nessun goto:

Fib\_1 = 0  
Fib\_2 = 1

Fib\_{2n} = Fib\_n^2 + Fib\_{n + 1}^2  
Fib\_{2n + 1} = Fib\_{n + 1} \cdot (Fib\_{n + 1} + 2Fib\_n)

[http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF](http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF)

Visto che parte da 0 e non da uno, N \le LLONG\_MAX - 1

---

<div class="post-metadata">

**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\
**Post date:** [29 Novembre 2017, 4:29pm UTC](https://forum.olinfo.it/t/numeri-di-figonacci-problema/4395/15 "2017-11-29T16:29:10Z")

</div>

è super necroposting, ma mi sono accorto adesso che se

> [@dp\_1](#):
>
> Fib2n=Fib2n+Fib2n+1Fib\_{2n} = Fib\_n^2 + Fib\_{n + 1}^2
> 
> Fib2n+1=Fibn+1⋅(Fibn+1+2Fibn)Fib\_{2n + 1} = Fib\_{n + 1} \cdot (Fib\_{n + 1} + 2Fib\_n)

mi verrebbe da dire allora questa congettura è vera

> [@lukecavabarrett](#):
>
> oserei una congettura tale che
> 
> f(n)=f(i)⋅f(n−i)+f(i−1)⋅f(n−i−1)f(n)=f(i)\cdot f(n-i)+f(i-1)\cdot f(n-i-1)