@*Intro. Given $m$, $n$, $t$, and $z$, I calculate the $z$th matrix with the property that \$0\le a_{i,j} #include int m,n,t; /* command-line parameters */ unsigned long long z; /* another command-line parameter */ char bad[maxt][maxt][maxt][maxt]; /* is a submatrix bad? */ unsigned long long *count; /* the big array of counts */ unsigned long long newcount[maxt]; /* counts that will replace old ones */ int firstknown; /* where the good information begins in |sol| */ unsigned long long mems; /* memory references to octabytes */ int inx[maxn+1]; /* indices being looped over */ int tpow[maxn+2]; /* powers of |t| */ int pos[maxn+1]; /* what solution position corresponds to each index */ int sol[maxn*maxn]; /* the partial solution known so far */ main(int argc,char*argv[]) { register int a,b,c,d,i,j,k,p,q,r,pp,p0; @; @; firstknown=m*n; /* nothing is known at the beginning */ loop:@+while (firstknown) { for (i=1;i; @; } @; } @ @= if (argc!=5 || sscanf(argv[1],"%d", &m)!=1 || sscanf(argv[2],"%d", &n)!=1 || sscanf(argv[3],"%d", &t)!=1 || sscanf(argv[4],"%lld", &z)!=1) { fprintf(stderr,"Usage: %s m n t z\n", argv[0]); exit(-1); } if (m<2 || m>maxn || n<2 || n>maxn) { fprintf(stderr,"Sorry, m and n should be between 2 and %d!\n", maxn); exit(-2); } if (t<2 || t>maxt) { fprintf(stderr,"Sorry, t should be between 2 and %d!\n", maxt); exit(-3); } for (j=1,k=0;k<=n+1;k++) tpow[k]=j,j*=t; count=(unsigned long long*)malloc(tpow[n+1]*sizeof(unsigned long long)); if (!count) { fprintf(stderr,"I couldn't allocate t^%d=%d entries for the counts!\n", n+1,tpow[n+1]); exit(-4); } @ @= for (a=0;ab) goto nogood; if (a>b && c>d) goto nogood; if (a>b && b==d && d>c) goto nogood; continue; nogood: bad[a][b][c][d]=1; bad[a][c][b][d]=1; bad[b][d][a][c]=1; bad[b][a][d][c]=1; bad[d][c][b][a]=1; bad[d][b][c][a]=1; bad[c][a][d][b]=1; bad[c][d][a][b]=1; } @ @= fprintf(stderr,"Solution completed after %lld mems:\n", mems); for (i=0;i= for (k=0;k<=n;k++) { o,pos[q]=--firstknown; if (q==0) q=n;@+else q--; } for (p=0;p= for (r=0;r<=n;r++) if (r!=q && (o,pos[r]==0)) { ooo,inx[r]++, p+=tpow[r]; if (inx[r]= { if (j==1) @@; else q=(q==n? 0: q+1); while (1) { o,b=(q==n? inx[0]: inx[q+1]); o,c=(q==0? inx[n]: inx[q-1]); if (i*n+j>=firstknown) @@; else { for (d=0;d; if (p==p0) break; } if (i*n+j>=firstknown) ooo,pos[q]=i*n+1,inx[q]=sol[i*n+j],p+=inx[q]*tpow[q],p0=p; fprintf(stderr," done with %d,%d ..%lld, %lld mems\n", i,j,count[0],mems); } @ @= { d=sol[i*n+j]; if (i*n+j==firstknown+n) @; for (oo,newcount[d]=0,a=0,pp=p;a= { for (o,a=0,pp=p;a= { if (i==1) { o,p=q=0,newcount[0]=1; for (r=0;r<=n;r++) { if (r; if (p==p0) break; } }@+else { q=(q==n? 0: q+1); if (n*i==firstknown+n) @; while (1) { for (o,a=0,pp=p,newcount[0]=0;a=firstknown) o,count[p+sol[n*i]*tpow[q]]=newcount[0]; else@+for (a=0,pp=p;a; if (p==p0) break; } if (i*n>=firstknown) ooo,pos[q]=i*n,inx[q]=sol[i*n],p+=inx[q]*tpow[q],p0=p; q=(q==n? 0: q+1); } } @ @= { for (o,a=0,pp=p;a