Ciao a tutti, sto provando a risolvere Cicla e Moltiplica e il mio programma esegue correttamente tutti gli esempi, per poi dare output non corretti dopo al submit (a parte degli “execution timed out” nell’ultimo subtask).
Ero già riuscito a ottenere 10/100 a forza bruta, ma non riesco a far funzionare questa ottimizzazione:
#include <vector>
#include <iostream>
using namespace std;
long long int gcd(long long int a, long long int b)
{
if (b == 0) return a;
return gcd(b, a % b);
}
long long int power(long long int x, long long int y, long long int p)
{
long long int res = 1;
while (y > 0) {
if (y % 2 == 1) res = res * x;
y = y >> 1;
x = (x * x);
}
return res % p;
}
vector<int> execute(int N, int K, int D, vector<int> A) {
vector<int> B(N);
for (int i = 0; i < N; ++i) {
B[i] = 1;
}
long long int modulo = 1e9 + 7;
long long int mcd = gcd(N, D);
long long int C = N/(mcd);
long long int r = K % C;
for (int i = 0; i < N; i++) {
int k = i;
for (int j = 0; j < C; j++) {
if (j < r) {
B[i] = (B[i] * A[k]) % modulo;
}
B[i] *= power(A[k], K / C, modulo) % modulo;
//cicla
k = (k-D+N)%N;
}
}
return B;
}
Ho messo tutte le variabili come long long int per evitare l’overflowing, ma a quanto pare non è quello il problema.
Grazie!
