Форум умных людей

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 16
#define u16 unsigned short
#define u32 unsigned
#define max 20

typedef struct{u16 q[N];short nz;}u16N;
typedef struct{u16N u0,u1;}u16N2;
typedef struct{int n,g;}int2;
typedef struct{int len;int2* p;}int2arr;

u16N new16N(){u16N a;for(int i=0;i<N;i++)a.q[i]=0;a.nz=0;return a;}

int nZ(u16 q[N]){int cnt=N;for(int i=N-1;i>=0;i--)if(q[i])break;else cnt--;return cnt;}

u16N toU16N(u32 n){u16N a=new16N();a.q[0]=n;a.q[1]=(n>>16);a.nz=a.q[1]?2:(a.q[0]?1:0);return a;}

u16N sum(u16N a,u16N b){
    int m=a.nz>=b.nz?a.nz:b.nz;
    u16N s=new16N();
    u32 c=0;
    for(int i=0;i<m;i++){u32 t=c+a.q[i]+b.q[i];s.q[i]=t;c=t>>16;}
    if(c&&m<N)s.q[m]=1;
    s.nz=nZ(s.q);
    return s;
}

int cmp(u16N a, u16N b){
    int s=a.nz-b.nz;
    if(s)return s;
    for(int i=a.nz-1;i>=0;i--)if(s=a.q[i]-b.q[i])return s;
    return 0;
}

u16N inv(u16N a){
    u16N b;
    for(int i=0;i<N;i++)
    b.q[i]=~a.q[i];
    b.nz=nZ(b.q);
    return b;
}

u16N subt(u16N a, u16N b){return sum(a,sum(inv(b),toU16N(1)));}

u16N shL0(u16N a,int n){
    u16N b=new16N();
    u16 c=0;
    for(int i=0;i<a.nz;i++){u32 r=c|((u32)a.q[i]<<n);b.q[i]=r;c=r>>16;}
    if(a.nz<N)b.q[a.nz]=c;
    b.nz=nZ(b.q);
    return b;
}

u16N shL(u16N a,int n){
    u16N b=shL0(a,n&0xf);
    int n1=n>>4;
    if(n1)for(int i=a.nz;i>=0;i--){int j=i+n1;if(j<N)b.q[j]=b.q[i];if(i<N)b.q[i]=0;}
    b.nz=nZ(b.q);
    return b;
}

u16N shR(u16N a){
    u16N b=new16N();
    for(int i=a.nz-1;i>=0;i--){u32 u=(i==a.nz-1?0:a.q[i+1]);u32 w=(u<<16)|a.q[i];b.q[i]=(w>>1);}
    b.nz=nZ(b.q);
    return b;
}

int max1(u16N a){
    int k=-1;
    if(a.nz){for(int i=15;i>=0;i--)if((a.q[a.nz-1]>>i)&1){k=i;break;}k+=(a.nz-1)<<4;}
    return k;
}

u16N2 div2(u16N a,u16N b){
    u16N2 res;
    res.u0=new16N();
    int d=max1(a)-max1(b);
    if(d<0){res.u1=a;return res;}
    u16N bb=shL(b,d);
    if(cmp(a,bb)>=0){res.u0=toU16N(1);a=subt(a,bb);}
    while(cmp(bb,b)){
        bb=shR(bb);
        res.u0=shL(res.u0,1);
        int k=cmp(a,bb);
        if(k>=0){if(!res.u0.nz)res.u0.nz=1;res.u0.q[0]|=1;a=subt(a,bb);}
    }
    res.u1=a;
    return res;
}

void show(u16N a){
    if(!a.nz){printf("0\n");return;}
    int d[(int)(N*1.25)+1];
    int cnt=0;
    u16N b=toU16N(1000000);
    while(a.nz){u16N2 c=div2(a,b);d[++cnt-1]=c.u1.q[0]+((u32)c.u1.q[1]<<16);a=c.u0;}
    printf("%d",d[cnt-1]);
    for(int i=cnt-2;i>=0;i--)printf(" %06d",d[i]);
}

int2arr f(int n,int l){
    int q[max-1];
    int cnt=0;
    for(int i=0;i<l;i++)
        if((n>>i)&1)q[++cnt-1]=i;
    int q1[max],s[max];
    int cnt1=0;
    for(int i=0;i<cnt;i++)
        if(i==0){q1[0]=q[0];q1[1]=q[0]+1;s[0]=s[1]=1;cnt1=2;}
        else{
            if(q[i]==q1[cnt1-1])s[cnt1-1]++;
            else{q1[++cnt1-1]=q[i];s[cnt1-1]=1;}
            q1[++cnt1-1]=q[i]+1;s[cnt1-1]=1;
        }
    int2arr a;
    a.len=1<<cnt1;a.p=(int2*)malloc(a.len*sizeof(int2));
    for(int i=0;i<a.len;i++){
        int g=0;int n=0;
        for(int j=0;j<cnt1;j++){int k=(i>>j)&1;n|=k<<q1[j];if(k&&s[j]>1)g++;}
        a.p[i].n=n;a.p[i].g=g;
    }
    return a;
}

char* hms(char* time){
    char* hms=(char*)malloc(9*sizeof(char));
    for(int i=0;i<8;i++)hms[i]=time[i+11];
    hms[8]='\0';
    return hms;
}

int main(){
    printf("max=%d\n\n",max);
    int l=1;
    u16N* m=(u16N*)malloc(2*sizeof(u16N));
    m[0]=toU16N(0);m[1]=toU16N(1);
    while(l<max){
        int size=1<<l;
        int size1=1<<(l+1);
        u16N* m1=(u16N*)malloc(size1*sizeof(u16N));
        for(int i=0;i<size1;i++)m1[i]=new16N();
        for(int i=0;i<size;i++){
            int2arr a=f(i,l);
            for(int j=0;j<a.len;j++)m1[a.p[j].n]=sum(m1[a.p[j].n],shL0(m[i],a.p[j].g));
            free(a.p);
        }
        free(m);m=m1;l++;
        u16N s=new16N();
        for(int i=0;i<size1;i++)s=sum(s,m1[i]);
        int tm=time(0);
        printf("%s",hms(ctime(&tm)));
        printf("%4d = ",l);
        show(s);printf("\n\n");
    }
    free(m);
    return 0;
}