Ciao, sto provando a ottenere 100 in cicla e moltiplica (shiftmul), ma purtroppo la soluzione implementata da errore di output in alcuni testcase. Non riesco però a trovare input da testare che risultino sbagliati. Ho pensato a un problema di overflow, ma non mi sembra, anche perché passano anche alcuni testcase dell’ultima subtask.
Ho aggiunto qualche commento al mio codice:
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
long long fastExp(long long base, long long exponent) {
if (exponent == 0) {
return 1;
} else if (exponent % 2 == 0) {
long long temp = (fastExp(base, exponent / 2))%mod;
return (temp * temp)%mod;
} else {
long long temp = (fastExp(base, exponent / 2))%mod;
return (((temp * temp)%mod) * base)%mod;
}
}
vector<int> execute(int N, int K, int D, vector<int> A) {
vector<int> B (N, 1);
vector<int> E;
E.push_back(0);
int next = D == 0 ? 0 : N-D;
while (next != E.front()) { // ottengo nel vettore E la successione deli indici dati dal ciclo
E.push_back(next);
next -= D;
if (next < 0) {
next = N + next;
}
}
long long cicli = K/E.size(); // numero di cicli completi
long long scarto = K%E.size(); // lunghezza del ciclo incompleto
vector<bool> visied(N, false);
for (int i=0; i<N; i++) {
if (visied[i]) {
continue;
} else {
long long n = 1;
for (int j=0; j<E.size(); j++) { // calcolo il fattore comune a tutti gli elementi del ciclo
n = (n * (fastExp(A[(E[j]+i)%N], cicli)))%mod;
}
int p = 1;
for (int j=0; j<scarto; j++) { // calcolo l'ulteriore fattore da moltiplicare dato dal ciclo incompleto (partendo da quello del primo elemento)
p = (p * (A[(E[j]+i)%N]))%mod;
}
for (int j=0; j<E.size(); j++) {
B[(E[j]+i)%N] = (n*p)%mod; // assegno il valore finale
visied[(E[j]+i)%N] = true;
p = (p * fastExp((A[(E[j]+i)%N]), mod-2))%mod; // divido p per l'elemento corrente
p = (p * (A[(E[(j+scarto)%E.size()]+i)%N]))%mod; // moltiplico per l'elemento successivo nella serie di scarto per ottenere il nuovo fattore dato dallo scarto
}
}
}
return B;
}
Grazie in anticipo!
