Cicla e moltiplica (shiftmul)

ciao, molto probabilmente ho sbagliato qualcosa di stupido, però ci sto sbattendo la testa e non capisco come è possibile che mi dia gli esempi giusti e tutti gli altri testcase sbagliati. Il ragionamento mi sembra corretto, magari si può ottimizzare qualcosa, però questo è:

ll fastexp(int a, int b){
    if (b == 0) return 1;
    ll x = fastexp(a, b/2);
    if(b % 2 == 0) return (x * x) % mod;
    return (x * x * a) % mod;
}


void moltiplica(vector<int> &a, vector<int> &b) {

    for(int i = 0; i < a.size(); ++i){
        ll x = (b[i] * a[i]) % mod;
        b[i] = x;
    }

}

void cicla(vector<int> &a, int D){

    vector<int> copia(a.size());

    for(int i = 0, d = D % a.size(); i < a.size(); ++i, ++d%= a.size()){
        copia[d] = a[i];
    }

    a = copia;
}

vector<int> execute(int n, int k, int d, vector<int> a){
    vector<int> b(n, 1);

    if(d){
        for(int i = 0; i < k%n; ++i){
            moltiplica(a, b);
            cicla(a, d);
        }

        int mol = 1;
        for(int i = 0; i < n; ++i){
            mol = (mol * a[i]) % mod;
        }
        mol = fastexp(mol, k/n);
        for(int i = 0; i < n; ++i){
            b[i] = (b[i] * mol) % mod;
        }
    }else{
        for(int i = 0; i < n; ++i){
            b[i] = fastexp(a[i], k);
        }
    }
    
    for(auto &x : b){
        x %= mod;
    }

    return b;
}

int main() {
    fast();

    int n, k, d; cin>>n>>k>>d;
    vector<int> v(n);
    for(int i = 0; i < n; ++i){
        cin >> v[i];
    }

    vector<int> sol = execute(n, k, d, v);

    for(auto x : sol){
        cout << x << " ";
    }

    return 0;
}

in pratica visto che ciclando il vettore con k > n si incontrano gli stessi numeri moltiplico b per quei numeri moltiplicati insieme e tutto elevato a quanti giri fa k in n (k/n) l’eccesso lo faccio all’inizio.
dove sbaglio?

Overflowi dappertutto. Ricordati che se moltiplichi due int il tipo di ritorno della moltiplicazione è int, questo indipendentemente dal fatto che il prodotto stia in un int o meno.

adesso ricontrollo per bene, mi complica un sacco il fatto che mi da come parametri interi e vuole returnato un intero, non posso cambiarli quelli giusto? senno per me metterei pure tutti long long​:joy:, comunque per evitare sti overflow e comunque mantenere gli interi, che devo fare?? La mia idea al momento è mettere ll(“variabile int”) nelle moltiplicazioni per ottenere i valori long long per poi modularli e inserirli nella variabile int. A proposito, se faccio var_int = var_long_long assumendo che la variabile long long stia in un intero, va bene? oppure devo fare var_int = int(var_long_long). grazie comunque :grin:

p.s. ho provato a modificare un po’ di robe ma comunque non va, io prima di creare l’argomento qui sul forum, avevo pensato all’overflow, ma comunque non pensavo perchè provando localmente un input del genere:
10 1000000000 7
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

l’algoritmo outputta regolarmente:
331080211 331080211 331080211 331080211 331080211 331080211 331080211 331080211 331080211 331080211 che non so se è la soluzione, ma comunque sono numeri sotto 10^9 e quindi avevo escluso l’overflow… boh non capisco cosa sbaglio, se potete aiutarmi ne sarei grato.

Beh quando overflowi comunque il risultato viene messo dentro a un int quindi chiaramente non otterrai numeri più grossi di 2^{31}. Inoltre tu poi stai prendendo quei valori sotto modulo e quindi chiaramente il programma stamperà interi nel range [0, 10^9+7).

Per quanto riguarda le conversioni tra tipi è estremamente semplice:

int x = 1;
long long y = 1; // è sempre valido, perché un long long può sempre contenere un int

long long y = 1e9;
int x = y; // è valido, ma overflowa se y non sta in un int

int y = 1e5;
int x = y * y % MOD // overflowa sicuramente, perché y * y non sta in un int

int y = 1e5;
int x = (long long)y * y % MOD; // non overflowa, perché y viene convertito a long long e il risultato finale sta in un int (garantito dalla riduzione modulo 1e9+7)
int fastexp(int a, int b){
    if (b == 0) return 1;
    int x = fastexp(a, b/2);
    if(b % 2 == 0) return ((ll)x * x) % mod;
    return ((ll)x * x * a) % mod;
}


void moltiplica(vector<int> &a, vector<int> &b) {

    for(int i = 0; i < a.size(); ++i){
        b[i] = ((ll)b[i] * a[i]) % mod;
    }

}

void cicla(vector<int> &a, int D){

    vector<int> copia(a.size());

    for(int i = 0, d = D % a.size(); i < a.size(); ++i, ++d%= a.size()){
        copia[d] = a[i];
    }

    a = copia;
}

vector<int> execute(int n, int k, int d, vector<int> a){
    vector<int> b(n, 1);

    if(d){
        for(int i = 0; i < k%n; ++i){
            moltiplica(a, b);
            cicla(a, d);
        }

        int mol = 1;
        for(int i = 0; i < n; ++i){
            mol = ((ll)mol * a[i]) % mod;
        }
        mol = fastexp(mol, k/n);
        for(int i = 0; i < n; ++i){
            b[i] = ((ll)b[i] * mol) % mod;
        }
    }else{
        for(int i = 0; i < n; ++i){
            b[i] = fastexp(a[i], k);
        }
    }
    

    return b;
}

hai scritto in maniera chiarissima, ma ancora non va, mi sento un sacco stupido non capisco, ogni moltiplicazione che faccio adesso la faccio con un termine in long long, quindi dovrebbe essere long long anche il risultato, poi è modulato in 10^9 + 7 e infine è messa in un intero. Non ci dovrebbero nemmeno essere problemi con la funzione cicla, anche perchè nella subtask 3 d = 0, dove uso solamente la fastexp. quindi il problema penso si trovi proprio li… ma non capisco dove. Scusami se faccio fatica ad arrivare al punto🙄

x * x * a può overfloware anche un long long, devi ridurre dopo ogni moltiplicazione.

ah vero non ci ho pensato, uso sempre sta funzione e davo per scontato funzionasse. Ora ho problemi di tempo, è lenta la funzione cicla oppure si può migliorare ancora il metodo di moltiplicazione? Comunque grazie ancora per l’aiuto

Un buon passo per capire cosa si può ottimizzare è calcolare la complessità della soluzione attuale.

1 Mi Piace

Qualcosa devi rivedere anche a livello di logica, il tuo algoritmo non processa correttamente questo input, ad esempio:
4 5 2
1 2 3 4

1 Mi Piace

in merito alle risposte che mi avete dato (vi ringrazio tral’altro), ho tirato giù questo algoritmo:

int fastexp(int a, int b){
    if (b == 0) return 1;
    int x = fastexp(a, b/2);
    if(b % 2 == 0) return ((ll)x * x) % mod;
    return ((((ll)x * x) % mod) * a) % mod;
}

int gcd(int a, int b){
    if (a < b) return gcd(b, a);
    if(b == 0) return a;
    return (gcd(b, a%b));
}

void moltiplica(vector<int> &a, vector<int> &b) {

    for(int i = 0; i < a.size(); ++i){
        b[i] = ((ll)b[i] * a[i]) % mod;
    }

}

void cicla(vector<int> &a, int D){

    vector<int> copia(a.size());

    for(int i = 0, d = D % a.size(); i < a.size(); ++i, ++d %= a.size()){
        copia[d] = a[i];
    }

    a = copia;
}

vector<int> execute(int n, int k, int d, vector<int> a){

    vector<int> b(n, 1);

    if(!d){
        for(int i = 0; i < n; ++i){
            b[i] = fastexp(a[i], k);
        }
    }else{
        int cicli = n / gcd(n, d);

        for(int i = 0; i < k % cicli; ++i){
            moltiplica(a, b);
            cicla(a, d);
        }

        int dist = n / cicli;
        vector<int> tot(dist, 1);

        for(int i = 0; i < n; ++i){
            tot[i % dist] = ((ll)tot[i%dist] * a[i]) % mod;
        }

        for(auto &x : tot){
            x = fastexp(x, k / cicli);
        }

        for(int i = 0; i < n; ++i){
            b[i] = ((ll)b[i] * tot[i % dist]) % mod;
        }
    }
    

    return b;
}

int main() {
    fast();

    int n, k, d; cin>>n>>k>>d;
    vector<int> v(n);
    for(int i = 0; i < n; ++i){
        cin >> v[i];
    }

    vector<int> sol = execute(n, k, d, v);

    for(auto x : sol){
        cout << x << " ";
    }

    return 0;
}


ora è corretto, fa quello che deve fare, ma in modo troppo lento. Questo è il massimo che sono riuscito a fare:
image
Come mi è stato consigliato ho calcolato la complessità del mio algoritmo ed essa risulta
O(n^2) con d \neq 0 e O(n \cdot log (k)) con d = 0 .
Il problema di questa complessità quadratica sta nel calcolo dell’eccesso. In poche parole l’algoritmo prima calcola la parte variabile e aciclica del vettore e poi una costante, esponenziandola al numero di volte in cui si ripete, e moltiplicata all’eccesso. solo che l’eccesso lo faccio “manualmente” ovvero calcolo in un for fino a k \% cicli (dove cicli può essere al massimo n quindi k massimo n-1), e dentro il for metto funzione moltiplica e cicla entrambe O(n) , non riesco a pensare ad un metodo per calcolarmi più velocemente l’eccesso… Per adesso penso si possa usare qualche ricorsione ma non so come.

I TLE che riscontri sono riconducibili ai casi in cui D = 1 o gcd(N,D) = 1, quindi ti potresti concentrare solo su queste 2 condizioni che sono equivalenti.
Pertanto come hai ben capito il problema è di complessità e di come calcolare la parte in eccesso K%cicli nel caso peggiore che comporta un ciclo for() fino ad un massimo di N-1 le funzioni cicla() e moltiplica().
Per calcolare la parte in eccesso non serve una qualche ricorsione che, probabilmente, peggiorerebbe solo la complessità ma utilizzare, opportunamente, la Modular Multiplicative Inverse che puoi, ad esempio, approfondire qui, una tecnica ricorrente e utile in ambito competitive-programming.

1 Mi Piace

ah, stavo buttando la spugna ormai, grazie mille, approfondirò la tecnica e vi faccio sapere quando lo risolvo, comunque mi sorge un dubbio, tutte queste tecniche dove le trovo? c’è un corso o qualcosa che ti fa fare a 360 gradi tutte le tecniche e gli argomenti della cp in modo specifico? proprio come se fosse un programma di matematica, perchè so le cose generali e le tecniche avanzate più importanti, e non riesco a capire come studiare per bene per ottenere sicurezza e saper approcciare al meglio ogni problema. Vorrei diventare bravo ma mi sento di vagare un pò nel vuoto, ho provato a leggere il CPH e sicuramente continuerò li ma mi sembra molto generale e non ho pratica su cui esercitarmi dopo aver letto li la teoria… se potete aiutarmi anche in questo ve ne sarei molto grato.

P.S. non so se potevo chiedere cose non inerenti al problema su cui ho creato l’argomento, nel caso crea problemi creerò un altro argomento😊

1 Mi Piace

Ho appena notato che quel sito che cercavo è praticamente quello che mi hai mandato tu, comunque se avete altre risorse le aspetto con pazienza, ti metto la soluzione appena risolvo il problema, sto ancora capendo come usare l’inverso modulare.

Prova a dare uno sguardo anche a questa pagina.