sto cercando di puntare al 100 su gcd,sono partito da una dp ON*N*K*complex(gcd) calcolandomi il numero di combinazioni che arrivano ad un determinato indice per poi moltiplicarle per il gcd che sto considerando ottenendo per tanto delle nuove configurazioni con K+1 raggrupamenti il problema è che francamente non riesco a capire dove sfori il mod e come sia possibile soltanto in dp arrivare a una sol generale che totalizzi 100 senza l utilizzo di magia nera(ds particolari o algoritmi per il gcd)
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
unsigned long long int dp[50001][20],counter[50001][20];
int main(){
unsigned long long int N,K,sum=0;
cin>>N>>K;
unsigned long long int vet[N];
for(int i=0;i<N;i++)cin>>vet[i];
counter[0][0]=1;
for(int i=1;i<N;i++)counter[0][i]=((i+1)+counter[0][i-1])%mod;
for(int i=1;i<K;i++){
counter[i][i]=1;
for(int j=i+1;j<N;j++){
counter[i][j]=((((counter[i][j-1]-counter[i][j-2]+mod)%mod)+counter[i-1][j-1])%mod+counter[i][j-1])%mod;
}
}
for(int i=0;i<N;i++){
dp[0][i]+=vet[i];
unsigned long long int sgcd=vet[i];
for(int j=i-1;j>=0;j--){
sgcd=__gcd(sgcd,vet[j]);
dp[0][i]+=sgcd;
dp[0][i]%=mod;
}
sum+=dp[0][i];
sum%=mod;
if(i!=0)dp[0][i]+=dp[0][i-1];
dp[0][i]%=mod;
}
if(K>1)sum=0;
for(int i=1;i<K;i++){
for(int j=i;j<N;j++){
unsigned long long int sgcd=vet[j];
for(int k=j-1;k>=0;k--){
if(k==i-2)break;
dp[i][j]+=(((counter[i-1][k])*(sgcd)%mod)+dp[i-1][k])%mod;
dp[i][j]%=mod;
sgcd=__gcd(sgcd,vet[k]);
}
if(i==K-1)sum+=dp[i][j];
sum%=mod;
dp[i][j]+=dp[i][j-1];
dp[i][j]%=mod;
}
}
cout<<sum;
}
Ad ogni nuovo gcd calcolato ottengo un risultanto <= gcd attuale questo vuol significare che posso ridurre la complex a un radical / log N, il prob ,é che avevo giá pensato ad un approccio radical N ,che prendesse in considerazione il fatto che tra il gcd attuale a quello successivo ;il gcd prende valori per solo i divisori del numero successivo .
però non riesco a capire come questa informazione mi riesca a diminuire la complex quando nella N×N×K ;cercare di raggruppare ancora di più le soluzioni causa inevitabilmente che nella dp[i][j] non avrò piú tutte le combinazioni che si conculudono con un raggrupamento finente nella pos j;
Btw
Nel code sopra ho dimenticato qualcosa?da ancora 20/100 ma non riesco a capire perché mi sbaglia casi con N>10
io sono a 49, comunque per evitare overflow somma prima (counter[i-1][k])*(sgcd)%mod e poi dp[i-1][k]( quindi in 2 operazioni separate). poi nel dubbio aggiungi moduli ovunque( dove non ci sono già)
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
long long int dp[50001][20],counter[50001][20];
int main(){
long long int N,K,sum=0;
cin>>N>>K;
long long int vet[N];
for(int i=0;i<N;i++)cin>>vet[i];
counter[0][0]=1;
for(int i=1;i<N;i++)counter[0][i]=((i%mod+1)%mod+counter[0][i-1]%mod)%mod;
for(int i=1;i<K;i++){
counter[i][i]=1;
for(int j=i+1;j<N;j++){
counter[i][j]=(((((counter[i][j-1]%mod-counter[i][j-2]%mod+mod)%mod)%mod+counter[i-1][j-1]%mod)%mod)%mod+counter[i][j-1]%mod)%mod;
}
}
for(int i=0;i<N;i++){
dp[0][i]+=vet[i];
long long int sgcd=vet[i];
for(int j=i-1;j>=0;j--){
sgcd=__gcd(sgcd,vet[j]);
dp[0][i]+=sgcd;
dp[0][i]%=mod;
}
sum+=dp[0][i]%mod;
sum%=mod;
if(i!=0)dp[0][i]+=dp[0][i-1]%mod;
dp[0][i]%=mod;
}
if(K>1)sum=0;
for(int i=1;i<K;i++){
for(int j=i;j<N;j++){
long long int sgcd=vet[j];
for(int k=j-1;k>=0;k--){
if(k==i-2)break;
dp[i][j]+=counter[i-1][k]%mod*(sgcd%mod)%mod;
dp[i][j]%=mod;
dp[i][j]+=dp[i-1][k]%mod;
dp[i][j]%=mod;
sgcd=__gcd(sgcd,vet[k]);
}
if(i==K-1)sum+=dp[i][j]%mod;
sum%=mod;
dp[i][j]+=dp[i][j-1]%mod;
dp[i][j]%=mod;
}
}
cout<<sum%mod;
Probabilmente anche se gli indici non sono usati correttamente puntano ad un area di memoria allocata. Tipo hai una tabella dp[5][5] e fai l’accesso in dp[0][10].
ok ho fatto 100 semplicemente non avevo capito a pieno una cosa banale che preso il gcd avrai una ripetizioni di certi valori btw nel complesso è divertente come prob ^^