test-38 solution hackerrank

                          test-38 solution hackerrank

 

1)

#include <stdio.h>

#define P 1000000007LL

long long I,g,b[1000], r,h,a[2000000],i,j,k,l,m,n, s[2000000],t,min, v[200000];

long long obsah(long long nn)
{
long long vv=1, ii;

for(ii=0;ii<k;ii++) vv = (vv*(b[ii]/nn))%P;

return vv;
}

long long next(long long jj)
{
long long kk,ii, ne;

kk = b[0]/jj;

ne = b[0]/kk + 1;

for(ii=1;ii<k;ii++)
 {
  kk = b[ii]/jj;
  
   if(ne > b[ii]/kk +1) ne = b[ii]/kk + 1;
 }


return ne;
}


int main()
{

scanf("%lld",&t);

while(t)
{
t--;

scanf("%lld",&k);
for(i=0;i<k;i++) scanf("%lld",b+i);

min = b[0];
for(i=0;i<k;i++) if(min>b[i]) min = b[i];


//printf("zac\n");

//a[0] = 1;
//s[0] = obsah[1];
j = 1;
l = 0;

while(1)
{
//printf("%lld =j\n",j);
a[l] = j;
s[l] = obsah(j);
l++;

if(j>min) break;

j = next(j);
}


for(m=l-1;m>=0;m--) 
  {
  v[m] = s[m];
  
  i = 2;
  h = 1;
  
  while(i*a[m] <= min)
   {
   
   while(a[m]*i >= a[h+1]) h++;

//  printf("%lld=m %lld=i %lld=h\n",m,i,h);
   
   I = (a[h+1]-1)/a[m];
   
   g = (I-i+1);

//  printf("%lld=m %lld=i %lld=h %lld=I %lld=g\n",m,i,h,I,g);

// return 0;
   
   v[m] = (v[m] - v[h]*g)%P;
   
   i=I+1;
   }
  
   v[m] = (v[m]+P)%P;  
  }


//for(i=0;i<l;i++) printf("%lld: %lld %lld -> %lld\n", i, a[i], s[i], v[i]);

  r = 0; 
  i = 1;
  h = 0;
  
  while(i <= min)
   {
//   printf("...%lld=i %lld=h\n",i,h);
   
   while(i >= a[h+1]) 
     {
      h++;
//      printf("kkk\n");
     }
 
   I = a[h+1]-1;
   
   g = (I-i+1)*(I+i)/2;

//  printf("....%lld=m %lld=i %lld=h %lld=I %lld=g\n",m,i,h,I,g);

// return 0;
   
   r = (r + v[h]*g)%P;
   
   i=I+1;
   }
  
   printf("%lld\n",r);   




}



return 0;
}

2)

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define MOD 1000000007
#define MAX 1001

 int N, M,i,j,nPieces = 4;
int pieces[] = {1, 2, 3, 4};
long long RowComb[MAX],ColumnComb[MAX],ColumnCombWithNoHoles[MAX];

void logic()
{
    scanf("%d %d",&N,&M);
    
    memset(RowComb, 0, sizeof(RowComb));
    RowComb[0] = 1;
    for (i = 1; i <= M; i++) {
        for (j = 0; j < nPieces; j++) {
            if (i - pieces[j] >= 0)
                RowComb[i] = (RowComb[i]+RowComb[i - pieces[j]]) % MOD;
        }
    }

    for (i = 1; i <= M; i++) {
        long long res = 1;
        for (j = 1; j <= N; j++) {
            res = (res *RowComb[i]) % MOD;
        }
        ColumnComb[i] = res;
    }
    ColumnCombWithNoHoles[1] = ColumnComb[1];
    for (i = 2; i <= M; i++) {
        ColumnCombWithNoHoles[i] = ColumnComb[i];
        for (j = 1; j < i; j++) {
            ColumnCombWithNoHoles[i] = (MOD + ColumnCombWithNoHoles[i]-(ColumnCombWithNoHoles[j] * ColumnComb[i - j]) % MOD) % MOD;
        }
    }

    printf("%lld\n",ColumnCombWithNoHoles[M]);
     
}

int main() {
    int T;
 scanf("%d",&T); 
 while(T--) logic();   
    return 0;
}



3)

#include <stdio.h>

long long a[300][300],s[300][300],i,j,k,l,m,n,p[20000],v, b[300][300], zas[500][2];


void obdlzdnik(long long xx, long long yy, long long dx, long long dy)
{

//printf("%lld: %lld %lld %lld %lld - > %lld\n", p[k],  xx, yy, dx, dy, dx*dy);

if(dx*dy > v) v = dx*dy;

return ;
}


void makaj()
{
long long ii,jj,kk,ll;

//printf("%lld\n",p[k]);


for(jj=0;jj<m;jj++) 
   if(a[0][jj] ==0) b[0][jj] = 1;
               else b[0][jj] = 0;

for(ii=1;ii<n;ii++)
 for(jj=0;jj<m;jj++)
  if(a[ii][jj] == 0) b[ii][jj] = b[ii-1][jj] + 1;
               else  b[ii][jj] = 0;

for(ii=0;ii<n;ii++) b[ii][m] = 0;


//printf("tui\n");

for(ii=0;ii<n;ii++) 
{
  zas[0][0] = 0;
  zas[0][1] = -1;

  ll = 0;

  for(jj=0;jj<=m;jj++)
   {
   while(b[ii][jj] < zas[ll][0])
     {
     obdlzdnik(ii - zas[ll][0] + 1, zas[ll][1], zas[ll][0], jj - zas[ll][1]);
     ll--;
     }
   
   if(zas[ll][0] < b[ii][jj]) 
     {
     ll++;
     zas[ll][0] = b[ii][jj];
     zas[ll][1] = jj;   
     }
   
   }



}

return;
}

int main()
{

for(i=2;i<20000;i++)
 if(p[i]==0) 
  for(j=i;j<=20000;j+=i) p[j] = i;

scanf("%lld %lld", &n, &m);

for(i=0;i<n;i++)
 for(j=0;j<m;j++) scanf("%lld",&(s[i][j]));
 
v = 0; 
k = 2;

//printf("tu\n");

while(k<=10000)
{
if(p[k] != k) {k++; continue;}

for(i=0;i<n;i++)
 for(j=0;j<m;j++) a[i][j] = s[i][j] % p[k];

makaj();

k++;
}



printf("%lld\n",v);

return 0;
}