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?
#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;
}
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?
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.
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.
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)?
#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}: