su cicla e moltiplica ottengo 50/100 perchè non riesco a risolvere 3 sottoposizioni della subtask 5, sapreste dirmi se nel mio codice mi sono dimenticato di una condizione particolare?
#include <iostream>
#include <vector>
using namespace std;
#define ull unsigned long long
#define mod 1000000007
int gcd(int a, int b){
if(b==0){
return a;
}else{
return gcd(b, a%b);
}
}
ull power(ull a, ull b)
{
ull result = 1;
while (b)
{
if (b & 1)
{
result = (result * a) % mod;
}
a = (a * a) % mod;
b >>= 1;
}
return result;
}
vector<int> solve2(int N, int K, int D, vector<int> A)
{
int cCompleti = K / (N / gcd(N, D));
ull num=1;
vector<int> B(N, 1);
for (int w = 0; w < gcd(N, D); ++w)
{
// 1) Valore comune dato da rotazioni complete
// Trovare valore comune al ciclo corrispondente
num = 1;
for (int i = w; i < N && cCompleti > 0; i += gcd(N, D))
{
num *= power(A[i], cCompleti);
num %= mod;
}
// cout<<cCompleti<<" "<<num<<'\n';
// iniziallizza B con valore comune
for (int i = w; i < N; i += gcd(N, D))
{
B[i] = num;
}
// 2)aggiunta della rotazione incompleta
int inizio = w;
num = 1;
// calcolo l'intervallo da cui si parte per moltiplicaare il primo elemento
int temp = K;
while (temp % (N / gcd(N, D)))
{
num *= A[inizio];
inizio -= D;
if (inizio < 0)
inizio += N;
temp--;
}
//cout<<num<<" "<<inizio<<'\n';
// se inizio == w allora nessun elemento rimanente
if (K % (N / gcd(N, D)) == 0)
{
continue;
}
// sposto l'intervallo di uno in uno
int j = w;
do
{
B[j] = ((ull)B[j] * num) % mod;
inizio += D;
inizio %= N;
num /= A[inizio];
j += D;
j %= N;
num *= A[j];
} while (j != w);
}
return B;
}
vector<int> solve1(int N, int K, int D, vector<int> A)
{
int cCompleti = K / N;
ull num = 1;
// 1) Valore comune dato da rotazioni complete
// Trovare valore comune //cicli completi>0
for (int i = 0; i < N && cCompleti > 0; ++i)
{
num *= power(A[i], cCompleti);
num %= mod;
}
// cout<<num<<'\n';
// iniziallizza B con valore comune
vector<int> B(N, num);
// 2)aggiunta della rotazione incompleta
int inizio = 0;
num = 1;
// calcolo l'intervallo da cui si parte per moltiplicaare il primo elemento
int temp = K;
while (temp % N)
{
num *= A[inizio];
inizio -= D;
if (inizio < 0)
inizio += N;
// cout<<inizio<<endl;
temp--;
}
// cout<<num<<" "<<inizio<<" "<<K%N<<'\n';
// se inizio == 0 allora nessun elemento rimanente
if (K%N==0)
{
return B;
}
// sposto l'intervallo di uno in uno
int j = 0;
do
{
B[j] = ((ull)B[j] * num) % mod;
inizio += D;
inizio %= N;
num /= A[inizio];
j += D;
j %= N;
num *= A[j];
} while (j != 0);
return B;
}
vector<int> execute(int N, int K, int D, vector<int> A)
{
// Caso: nessun spostamento
if (D == 0)
{
vector<int> B(N);
for (int i = 0; i < N; ++i)
{
B[i] = power(A[i], K);
}
return B;
}
// spostamento non crea divisioni
if (gcd(N, D) == 1 || D==1)
{
return solve1(N, K, D, A);
}
return solve2(N, K, D, A);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k, d;
cin >> n >> k >> d;
vector<int> ris;
vector<int> A(n);
for (int i = 0; i < n; ++i)
{
cin >> A[i];
}
ris = execute(n, k, d, A);
for (int i = 0; i < n; ++i)
{
cout << ris[i] << " ";
}
cout << '\n';
return 0;
}