Ciao, sto provando a fare shiftmul. Con il mio programma faccio tutti i testcase tranne (come ho visto in altri post) 3 dell’ultimo subtask. Questo è il codice:
#include <bits/stdc++.h>
using namespace std;
#define I 1000000007
long long ext_euc(long long a, long long b, long long &x, long long &y){
if(b==0){
x=1;
y=0;
return 1;
}
long long x1,y1;
long long result= ext_euc(b,a%b,x1,y1);
x=y1;
y=(x1-y1*(a/b));
return result;
}
long long modexp(long long base,long long exp,long long mod){
long long result=1;
base%=mod; while(exp>0){
if(exp%2==1){
result=(result*base)%mod;
}
exp/=2;
base=(base*base)%mod;
}
return result;
}
vector<int> execute(int N, int K, int D, vector<int> A){
vector<int> B(0);
if(D==0||N==1){
for(long long i=0;i<N;i++)B.push_back(modexp(A[i],K,I));
return B;
}//0 1 2 3 4 D=1 K=6
if((D==1||(N/D)*D!=N)&&K>=N){
vector<long long> inv(N);
long long num1,mult=1,num2;
for(int i=0;i<N;i++){
long long x,y;
ext_euc(A[i],I,x,y);
inv[i]=(x%I +I)%I;
mult=(mult*A[i])%I;
}
num2=modexp(mult,(K/N),I);
for(int i=0;i<N;i++){
long long index=((i-D*(K%N))%N +N)%N;
if(K%N!=0){
num1=mult;
for(long long j=K%N;j<N;j++){
num1=(num1*inv[index])%I;
index=(index-D+N)%N;
}
}else num1=1;
B.push_back((num1*num2)%I);
}
}else if((N/D)*D==N&&K>=N/D){
long long index, num;
for(long long i=0;i<D;i++){
index=i;
num=1;
for(long long j=0;j<N/D;j++){
num=(num*A[index])%I;
index=(index-D+N)%N;
}
num=modexp(num,K/(N/D),I);
B.push_back(num);
}
for(long long i=D;i<N;i++){
B.push_back(B[i%D]);
num=1;
index=i;
for(long long j=0;j<K%(N/D);j++){
num=(num*A[index])%I;
index=(index-D+N)%N;
}
B[i]=(B[i]*num)%I;
}
for(long long i=0;i<D;i++){
num=1;
index=i;
for(long long j=0;j<K%(N/D);j++){
num=(num*A[index])%I;
index=(index-D+N)%N;
}
B[i]=(B[i]*num)%I;
}
}else{
for(int i=0;i<N;i++){
long long num=1,index=i;
for(long j=0;j<K;j++){
num=(num*A[index])%I;
index=(index-D+N)%N;
}
B.push_back(num);
}
}
return B;
}
E’ un po’ lungo ma i problemi (almeno credo) sono nel secondo if.
Come suggerito in altri post ho usato gli inversi modulari per calcolare lo scarto K%N che è univoco per ogni A[i], però questo non ha risolto i TLE.