@*Intro. Given \$m\$, \$n\$, and \$t\$, I calculate the number of matrices with \$0\le a_{i,j} #include int m,n,t; /* command-line parameters */ 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 */ unsigned long long mems; /* memory references to octabytes */ int inx[maxn+1]; /* indices being looped over */ int tpow[maxn+2]; /* powers of |t| */ main(int argc,char*argv[]) { register int a,b,c,d,i,j,k,p,q,r,pp; @; @; for (i=1;i; @; } @ @= if (argc!=4 || sscanf(argv[1],"%d", &m)!=1 || sscanf(argv[2],"%d", &n)!=1 || sscanf(argv[3],"%d", &t)!=1) { fprintf(stderr,"Usage: %s m n t\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; } @ Throughout the main computation, I'll keep the value of |p| equal to \$(|inx[n]|\ldots|inx[1]inx[0]|)_t\$. @= for (r=0;r<=n;r++) if (r!=q) { 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]); for (d=0;d; if (p==0) break; } fprintf(stderr," done with %d,%d ..%lld, %lld mems\n", i,j,count[0],mems); } @ And here's the tricky part that keeps the inner loop easy. I don't know a good way to explain it, except to say that a hand simulation will reveal all. @= { if (i==1) { for (o,p=tpow[n+1];p>0;p--) o,count[p-1]=1; q=0; }@+else { q=(q==n? 0: q+1); while (1) { for (o,a=0,pp=p,newcount[0]=0;a; if (p==0) break; } q=(q==n? 0: q+1); } } @ @= for (newcount[0]=0,p=tpow[n+1]-1;p>=0;p--) o,newcount[0]+=count[p]; printf("Altogether %lld 3VPs (%lld mems).\n", newcount[0],mems); @*Index.