Ciao a tutti, stavo provando a risolvere shiftmul ed ero arrivato ad un’idea del genere:
Tra i vari elementi dell’array si formano dei cicli e gli elementi adiacenti dello stesso ciclo saranno alla fine prodotti con K-1 elementi in comune e 1 solo diverso. Un approccio potrebbe essere calcolare solo un valore per ciclo e poi mano a mano calcolare i successivi dividendo per l’elemento che compare tra i fattori del valore già calcolato ma non del valore da calcolare e poi moltiplicando per l’elemento che invece compare solo nei fattori del valore che stiamo calcolando ma non saprei come fare delle divisioni, vista la necessità di utilizzare il modulo. Ero arrivato alla conclusione che, se non sapevo come dividere per un valore, potevo semplicemente evitare di moltiplicare quel valore all’inizio e avevo scritto questo codice:
#include <vector>
using namespace std;
const int MOD=1000000007;
int n, d;
int scorri(int val){
val-=d;
if(val<0){
val+=n*((-1*val/n)+1);
}
if(val==n){
val=0;
}
return val;
}
int indietro(int val){
val+=d;
val%=n;
return val;
}
int FastExp(int base, int esponente){
if(esponente==1){
return base%MOD;
}
long long temp;
if(esponente%2==0){
temp=FastExp(base, esponente/2);
return (temp*temp)%MOD;
}else{
temp=FastExp(base, esponente/2);
return (((temp*temp)%MOD)*base)%MOD;
}
}
vector<int> execute(int N, int K, int D, vector<int> A){
if(D==0 || D%N==0){ //Se D==0 o D è multiplo di N, basta elevare ogni elemento di A alla K
for(int i=0; i<N; i++){
A[i]=FastExp(A[i], K);
}
return A;
}
if(K==1){ //se K==1 allora semplicemente B sarà uguale ad A
return A;
}
d=D;
n=N;
vector<int> prefixMul(N+1), B(N, -1);
prefixMul[0]=1;
int stepFatti, stepRimanenti, index, lastIndex, numCicli, indexFinale;
long long temp, fattore, tempInd;
for(int pos=0; pos<N; pos++){
if(B[pos]==-1){ //Se la posizone attuale non è ancora stata visitata
index=pos;
stepFatti=1; //step fatti=1 perché ho già calcolato il primo valore (A[pos])
stepRimanenti=K-1;
prefixMul[1]=A[index]%MOD; //aggiorno i prodotti prefissi
index=scorri(index); //scorro al valore successivo
while(index!=pos && stepRimanenti>0){ //Scorro l'array finché non si ritorna sul valore iniziale (chiudendo un ciclo) o finché non si sono compiuti K cicli
stepFatti++;
stepRimanenti--;
temp=prefixMul[stepFatti-1]*A[index]; //salvo il prodotto prefisso temporaneamente in un long long per evitare overflow
temp%=MOD;
prefixMul[stepFatti]=temp; //aggiorno i prodotti prefissi
index=scorri(index);
}
index=indietro(index);
indexFinale=index;
lastIndex=-1;
//Il ciclo alla linea successiva riempirà gli elementi di B già esplorati nel ciclo precedentecon dei valori temporanei
while(lastIndex!=pos){ //Scorro l'array al contrario finché non torno al valore dal quale ho iniziato questo secondo ciclo (pos sarà l'ultimo visitato)
if(lastIndex==-1){ //prima iterazione di questo ciclo
B[index]=A[index]%MOD; //assegno il valore a B[index]
}else{
temp=B[lastIndex]*A[index];
temp%=MOD;
B[index]=temp; //assegno a B[index] un valore pari al prodotto tra B[index appena passato] e A[index]
}
lastIndex=index;
index=indietro(index);
}
fattore=1; //fattore sarà un numero che andrà moltiplicato ai vari valori temporanei per ottenere la risposta
if(stepRimanenti>stepFatti){ //Si possono fare ancora uno o più cicli
numCicli=stepRimanenti/stepFatti;
stepRimanenti-=stepFatti*numCicli;
fattore*=FastExp(B[pos], numCicli); //la base è B[pos] perché il valore di B[pos] è uguale al prodotto di tutti i valori esplorati
}
if(stepRimanenti>0){
fattore*=prefixMul[stepRimanenti]; //se si devono fare degli altri passaggi oltre ai cicli, si va avati moltiplicando per i prodotti prefissi
fattore%=MOD;
}
index=pos;
lastIndex=-1;
while(lastIndex!=indexFinale){ //Questo ciclo while continua finché non si è superato l'indice dell'ultimo elemento del ciclo
//moltiplico B[index] per il fattore
temp=B[index]*fattore;
temp%=MOD;
B[index]=temp;
//aggiorno index e lastIndex
lastIndex=index;
index=scorri(index);
//aggiorno fattore per il prossimo index
tempInd=(index-D*(K-1)); //perché il fattore sia corretto per il prossimo index servirà che il fattore venga moltiplicato per l'ultimo valore per cui verrebbe moltiplicato l'index
if(tempInd<0){
tempInd+=N*((-1*tempInd/N)+1);
}
if(tempInd==N){
tempInd=0;
}
fattore*=A[tempInd];
fattore%=MOD;
}
}
}
return B;
}
Solo che questo codice funziona solo nella subtask 2 (D=0, che ho gestito separatamente) e in alcuni testcase degli altri subtask (presumo anche loro con D=0).
Qualcuno saprebbe dirmi cosa non funziona?
Grazie