Cercando di risolvere Festival Del GCD ho scritto una soluzione bottom up tramite la programmazione dinamica con complessità O(N^2K), sono consapevole che non è sufficiente ma non posso proseguire se questa soluzione ha qualche WA, infatti faccio 20/100, ma in alcuni casi ottengo dei WA, anche se mi aspettavo solo TLE.
In pratica per ogni situazione del tipo [gruppi rimanenti][da questo indice in poi] computo in quanti modi differenti posso concludere la configurazione e quale somma totale mi danno. Per i modi mi baso sulla somma dei modi in cui posso concludere ogni altra situazione partendo da quella, mentre per quanto riguarda la somma totale moltiplico il GCD dell’intervallo che sto aggiungendo per il numero di modi in cui posso completare la configurazione, per poi aggiungere la somma dei valori della dp delle combinazioni successive.
#include<bits/stdc++.h>
using namespace std;
int const MAXN=51000, MAXK=22, MOD=1e9+7;
int n, k, v[MAXN], dp[MAXK][MAXN], c[MAXK][MAXN];
int gcd(int a, int b) { if(b!=0) return gcd(b,a%b); return a;}
int add(int a, int b) {return ((a%MOD)+(b%MOD))%MOD;}
int mult(int a, int b) {a%=MOD; b%=MOD; long long int res=(a*b)%MOD; return res;}
int main(){
cin>>n>>k;
for(int i=0;i<n;i++)
cin>>v[i];
for(int i=0;i<=n;i++)
c[0][i]=1;
for(int groups=1;groups<=k;groups++){
for(int i=n-1;i>=0;i--){
if(i<n-groups){ //Posso evitare di includere v[i] in un gruppo
dp[groups][i]=dp[groups][i+1];
c[groups][i]=c[groups][i+1];
}
int val=v[i];
for(int last=i;last+groups<=n;last++){
val=gcd(val,v[last]);
dp[groups][i]=add(dp[groups][i],dp[groups-1][last+1]);
dp[groups][i]=add(dp[groups][i],mult(val,c[groups-1][last+1]));
c[groups][i]=add(c[groups][i],c[groups-1][last+1]);
}
}
}
cout<<dp[k][0];
}
Qualcuno sa dirmi cosa mi sto perdendo? 