Ciao a tutti, stavo provando a risolvere shiftmul, ma mi dà 40/100(subtask D=0) e mi escono alcuni casi di output errato e la maggior parte TLE.
Cmq sono andato a vedere molti altri aiuti dati ad altre persone sul forum, ma non ho trovato niente che mi facesse trovare gli errori, quindi se riuscite ad aiutarmi vi ringrazio.
Io ho utilizzato la fast exponentiation per risolvere velocemente le potenze.
In execute:
- controllo se D=0 e se vero elevo B[i] alla K.
- controllo se N=1 ritorno A elevato alla K.
- controllo se K è divisibile per N allora moliplico B[i] per il prodotto degli N elementi di A elevato al quadrato (B[i] *= fastexp(product, 2) e K/=N.
- se K è ancora maggiore di N allora moltiplico B[i] * product e K-=N.
- eseguo B[i]A[(i+Dcount)%N quindi moltiplico B[i] con il relativo A[i] shiftato (non veramente) ogni volta A.
- shifto il vector B di (D*count-D)%N posizioni a dx → sottraggo D pk l’ultima rotazione di A non influenza il vector B.
Cmq, lasciando perdere i TLE(o se volete aiutarmi pure in quello ve ne sono grato), vorrei sapere come mai mi dà output errato… Grazie in anticipo.
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<numeric>
using namespace std;
const int MOD=1e9+7;
#define ll long long
//fast exponentiation --> speed up powers calculation
ll fastexp(ll a, ll b){
ll ans=1;
a%=MOD;
while(b>0)
{
if(b&1)
{
ans*=a;
ans%=MOD;
}
a*=a;
a%=MOD;
b/=2;
}
ans%=MOD;
return ans;
}
vector<int> execute(int N, int K, int D, vector<int> A)
{
vector<ll> B(N, 1);
if(D==0)
{
vector<int> v;
for(int i=0; i<N; i++)
{
v.push_back(fastexp(A[i], K));
}
return v;
}
//product of all elements in A[]
ll product = 1;
for(auto x: A)
product = (product * x) % MOD;
if(N == 1) return A[0] = fastexp(A[0], K), A;
int count=0;
//if K>N I multiplicate every B[i] by fastexp(product, 2) of all elements in A[]
while(K/N>=N)
{
for(int x=0; x<N; x++){
B[x]*=fastexp(product, 2);
B[x] %= MOD;
}
K/=N;
}
while(K>N)
{
for(int x=0; x<N; x++){
B[x]*=product;
B[x] %= MOD;
}
K-=N;
}
int last=K%N;
while(count<last)
{
//multiplicate B[i] by A[i+D]
for(int i=0; i<N; i++)
{
B[i]*=(ll)A[(i+D*count)%N]; //%N to get first positions (ex. N=5, i+d*count =6 --> gets 1^position)
B[i] %= MOD;
}
count++;
//for(int i=0; i<N; i++) cout<<B[i]<<" ";cout<<endl;
}
vector<int> v(N);
int rotate=(D*count)%N;
rotate-=D;
for(int i=0; i<N; i++)
{
v[i]=B[(N+i-rotate)%N];
}
return v;
}
int main(){
int N, K, D;
cin>>N>>K>>D;
vector<int>A(N);
for(int i=0; i<N; i++)cin>>A[i];
vector<int> B(N, 1);
B=execute(N, K, D, A);
for(int i=0; i<B.size(); i++)cout<<B[i]<<" ";
}