Fpb(20/100 15 caratteri)

Aiuto
1

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;
    }
2

Prendi tutte le sottosequenze che partono in un certo punto e guarda i loro GCD. Cosa puoi notare?
Ci sono tanti valori? Hanno un certo comportamento?

1 Mi Piace
3

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

Grazie per la risposta :smiley:

4

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à)

5 
#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;

}
20/100 battini lo spam di moduli non funziona :new_moon_with_face:

6 
      int64_t gcd(int64_t a, int64_t b) { return b == 0 ? a : gcd(b, a % b); } 
 ii td(int64_t i, int64_t g){
      if(g==0) return {0,1};
      if(i==n-1 && g==1) return {a[i],1};
      if(i==n-1 && g>1) return {-1,0};
      if(memo[i][g][0]!=-1) return memo[i][g];
      int64_t sum=0,d=a[i],c=0;
      for (size_t j = i; j < n-g+1; j++) {
        if(j+1==n) {
          c++;
          sum=(sum+d%md)%md;
          break;}
        ii tp=td(j+1,g-1);
        tp[0]=(tp[0]%md);
        if(tp[0]!=-1) {
            sum=((sum+tp[0]%md)%md)%md;
            sum=(sum%md+(d*tp[1]%md)%md)%md;
            sum=(sum%md);
        }
        c+=tp[1]%md;
        c=(c%md);
        if(d>1) d=gcd(d,a[j+1]);
      }
      if(i!=n-1 && i!=n-g){
      ii tp=td(i+1,g);
      if(tp[0]!=-1) sum=((sum+tp[0]%md)%md)%md;
      c+=tp[1];
    }
      return memo[i][g]={sum,c};
    }

Questo è la mia top down e il procedimento decritto ha risolto… hai messo i long long anche sul gcd?

7

si , ma letteramente pure nel code iniziale ho controllato tutto e non va nulla in overflow(teoricamente)

8

Se non sbaglio hai invertito i e j… dovrebbe essere dp[j][i], altrimenti vai fuori dalle dimensioni della matrice

9

ok anche se è un errore piuttosto sciocco perchè output non corretto invece di signal 11?

10

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].

11

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 ^^

2 Mi Piace