Shiftmul 50/100

Aiuto
1

Il mio programma riesce a risolvere tutti quanti gli input proposti, ma nel sub task 4 da alcuni risultati errati a causa del timeout. Non riesco a pensare ad alcun modo per rendere il tutto più veloce.

#include <vector>
#include <cstdio>
using namespace std;

long long int greatest_common_divisor(long long int n1, long long int n2) {
    if (n2==0) return n1;
    return greatest_common_divisor(n2, n1 % n2);
}

long long int expMod(long long int x, long long int y, long long int p) { //Faccio la potenza con O(log(y))
    long long int var = 1;

    while (y>0) {
        if (y%2==1) var=(var*x)%p; //Se è dispari moltiplica per X
        y=y/2; //Divide l'esponente per 2
        x=(x*x)%p; //Fa il quadrato dell'operazione corrente
    } //while

    var%=p; //Ritorna il modulo di var
    return var;
}

vector<int> execute(int N, int K, int D, vector<int> A) {
    //Creazione variabili
    int holdPos;
    const int mod=1e9+7;
    vector<int> B(N, 1);
    int startCount=N/greatest_common_divisor(N, D);//Quante volte torna alla posizione iniziale
    int extra=K%startCount; //Trova quanti sono i movimenti dopo l'ultima posizione iniziale


    for (int j=0; j<N; j++) { //Per ogni numero N

        holdPos = j;

        for (int i=0; i<startCount; i++) { //Per ogni ciclo

            if (i < extra) B[j] = ((B[j]%mod) * (A[holdPos]%mod)) % mod; //Gestisce i valori extra
            B[j] = ((B[j]%mod) * (expMod(A[holdPos], K/startCount, mod)%mod)) % mod;

            holdPos = holdPos - D;
            if (holdPos < 0) holdPos += N;
        } //I (Per ogni ciclo)

    } //J (N passaggi)

    return B;
}

Ho provato a cercare in giro cosa potrebbe rendere la mia soluzione più efficacie, e l’unica cosa che sono riuscito a trovare (ma non capire tantomeno applicare) era quella di risolvere parte dei calcoli fuori dai cicli utilizzando un valore che è pari al modulo di tutti i valori all’interno dell’array.

Qualunque tipo di indizio o aiuto su come procedere è apprezzato.
Grazie in anticipo.

2

Ho provato a modificare il mio programma utilizzando un nuovo metodo, ma ancora non riesce a risolvere il problema e continua a dare TLE, qualche idea?

#include <vector>
#include <cstdio>
using namespace std;

long long int greatest_common_divisor(long long int n1, long long int n2) {
    if (n2==0) return n1;
    return greatest_common_divisor(n2, n1 % n2);
}

long long int expMod(long long int x, long long int y, long long int p) { //Faccio la potenza con O(log(y))
    long long int var = 1;

    while (y>0) {
        if (y%2==1) var=(var*x)%p; //Se è dispari moltiplica per X
        y=y/2; //Divide l'esponente per 2
        x=(x*x)%p; //Fa il quadrato dell'operazione corrente
    } //while

    var%=p; //Ritorna il modulo di var
    return var;
}

vector<int> execute(int N, int K, int D, vector<int> A) {
    //Creazione variabili
    int holdPos;
    const int mod=1e9+7;
    vector<int> B(N, 1);

    int startCount=N/greatest_common_divisor(N, D);//Numero di cicli prima di tornare alla posizione iniziale
    int cycles=K/startCount; //Numero di cicli completi
    int extra=K%startCount; //Trova quanti sono i movimenti dopo l'ultima posizione iniziale

    vector<long long int> cycleProd(N, 1);
    vector<long long int> extraProd(N, 1);

    for (int i=0; i<N; i++) { //Per ogni numero N

        holdPos=i; //Tiene la posizione iniziale

        for (int j=0; j<startCount; j++) {

            if (j<extra) extraProd[i] = (extraProd[i] * A[holdPos]) % mod; //Calcola tutti i passaggi che non si ripetono

            cycleProd[i] = (cycleProd[i] * A[holdPos]) %mod; //Calcola tutti i passaggi che si ripetono
            holdPos=(holdPos-D+N)%N;

        } //J (per ogni passaggio prima di tornare alla posizione iniziale)

        cycleProd[i] = expMod(cycleProd[i], cycles, mod); //Fa l'esponente di tutti i passaggi che si ripetono in base a quante volte si ripetono
        B[i] = ((cycleProd[i]) * (extraProd[i])) %mod; //Moltiplica i passaggi che si ripetono e quelli che non si ripetono
    } //I (N passaggi)

    return B;
}

Qualunque aiuto è apprezzato.
Grazie in anticipo.

3

Sono riuscito a trovare una soluzione che riesce a non fare timeout, ma non riesco a capire per quale ragione sbaglia alcuni risultati.

#include <vector>

using namespace std;

vector<int> execute(int N, int K, int D, vector<int> A) {
    //Creazione variabili
    const int mod=1e9+7;
    vector<int> B(N, 1);
    vector<int> copyA=A;
    int newI = D;

    //Inizializza B e gestisci le potenze di A dinamicamente
    for (int i=0; K>0; i++, K>>=1) { //Per ogni ciclo, dimezzo K

        if (K&1) for (int j=0; j<N; j++) B[j] = static_cast<long long>(B[j]) * copyA[j] % mod; //Calcolo il nuovo B se K e' dispari

        //Aggiorna A per la prossima potenza di 2
        vector<int> newA(N);
        for (int j=0; j<N; j++) {
            const int newIndex = (j-newI+N)%N; //Calcola l'indice con spostamento D verso destra
            newA[j] = static_cast<long long>(copyA[j]) * copyA[newIndex] % mod; //Fa la moltiplicazione tra il nuovo e il vecchio A
        } //J

        copyA = newA; //Aggiorna A con la nuova potenza calcolata
        newI = (2*newI)%N;
    } //I

    return B;
}

Questa soluzione utilizza l’esponenziazione binaria (exponentiation by squaring) per trovare i risultati con una complessità O(N*log(K)), e riesce a risolvere molti casi ma ne sbaglia alcuni e non riesco a capire la ragione.
Riesce a risolvere tutti i casi dove D=0, il che mi fa pensare che il problema si presenta a causa dello spostamento.
Se riesco a risolvere questo problema prima di aiuti esterni, scriverò nel prossimo post come ho fatto a risolverlo nella speranza che qualcuno che ne avrà bisogno in futuro lo vedrà.

Qualunque aiuto è apprezzato.
Grazie in anticipo.