Fractal graphs 90/100

Aiuto
1

allora ho fatto due codici, il primo fatto totalmente da me che fa 90/100 ovvero il seguente:

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
#define mod 32749

void fast() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
}

void print(vector<int> const &input){ //se non usi vector<int> cambialo
    for (int i = 0; i < input.size(); i++) cout << input.at(i) << ' ';
}

ll nodi = 1, archi = 0; 
//triangolo = +2 nodi, +3 archi
//segmento = +2 nodi, +2 archi
//inserire nodi triangoli e a segmenti

void fractal_graph(ll n){
    nodi %= mod; archi %= mod;
    if(n == 0) {
        cout << nodi << " " << archi;
        return;
    }
    ll nodi_triangoli = (nodi * 2) % mod, archi_triangoli = (nodi * 3) % mod, nodi_segmenti = (archi * 2) % mod, archi_segmenti = (archi * 2) % mod;
    nodi +=( nodi_triangoli + nodi_segmenti) % mod;
    archi += (archi_triangoli + archi_segmenti) % mod;
    fractal_graph(n-1);
}

int main(){
    fast();
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    ll n; cin >> n;

    fractal_graph(n);

    return 0;
}

questo non riesce a fare gli ultimi testcase ovviamente per TLE, essendo che quando N > 50 000 000 l’algoritmo fa molta fatica visto che fa tante chiamate quanto è N

immagine_2023-10-28_113005691
immagine_2023-10-28_113005691562×525 10.1 KB

Mentre l’altro vedendo un pò qualche risposta sul forum riguardo questo problema, l’ho fatto scopiazzando qualche formula ovvero:

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
#define mod 32749

void fast() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
}

void print(vector<int> const &input){ //se non usi vector<int> cambialo
    for (int i = 0; i < input.size(); i++) cout << input.at(i) << ' ';
}

ll nodi = 1, archi = 0;
//triangolo = +2 nodi, +3 archi
//segmento = +2 nodi, +2 archi
//inserire nodi triangoli e a segmenti

void fractal_graph(ll n){
    if(n == 0) return;
    
    fractal_graph(n-1);
    ll temp = nodi;
    nodi = (nodi * 3) % mod + (archi * 2) % mod;
    archi = (temp * 3) % mod + (archi * 3) % mod;
    nodi %= mod;
    archi %= mod;

    return;


}

int main(){
    fast();
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    ll n; cin >> n;

    fractal_graph(n);
    
    cout<<nodi<<" "<<archi;
    return 0;
}

Questo fa 70/100 solo che non fa i testcase per “limite di memoria superato” però sembra che a velocità ci siamo:

image
image562×595 9.96 KB

Quindi vi chiedo:

  1. perchè il problema che fa 70/100 supera i limiti di memoria, e perchè anche avendo la stessa complessità del mio, è più veloce (mi viene da pensare che termina appena supera il limite e quindi non finisce tutte le chiamate però non so)
  2. c’è necessariamente bisogno di una formula matematica generale? se si come devo ragionare per tirarla fuori o comunque per induzione generarla dai casi più piccoli?
  3. è giusto spammare un pò ovunque i %mod? per stare sicuro li ho messi ovunque ma non so se possono essere un problema
1 Mi Piace
2
  1. Il tuo programma viene killato non appena raggiunge il limite di memoria.
  2. Con un po’ di teoria sulle ricorrenze lineari puoi tirare un formula chiusa abbastanza brutta ma calcolabile in O(\log N), tuttavia per risolvere le ricorrenze lineari di solito si usa una tecnica particolare, cioè esponenziazione di matrici (trovi una spiegazione a pagina 220 della bibbia).
  3. Sì i moduli vanno virtualmente ovunque se no rischi di overfloware.
3

Ho letto tutta la dispensa sulla ricorrenza lineare e sulle matrici. Ho provato anche ad applicare la teoria ma ho grossi problemi a costruire le matrici. Qui siamo in presenza di coppie di numeri, quindi non riesco proprio a capire come posizionarli all’interno di una matrice. Tralaltro non ho capito neanche bene come fa a costruire la matrice X nel caso generale. Grazie comunque per la risposta, se riesci ad aiutarmi ancora te ne sarei grato :blush:.