#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
typedef unsigned long long int U64;
//using namespace std;
    int next[800000];
    int buf0[800000];
    int res0[800000];
    int res1[800000];
    int buf1[800000];
int lookback;
int ii;
int offset;
int find_next(int max,int count,int buf_in[8000],int res_in[8000],int num_in,int buf_out[8000],int res_out[8000]){
    int i,j;
    int k=0;
    int tmp;
    int res;
    int res1;
    static int mult;
    int div=max*2-count;
    if (count==0) mult=1;
    else mult*=2*max-count+1;
    //printf("nult=%d\n",mult);
    i=0;
    //for(i=0;i<max*2-count;i++){
        for(j=0;j<num_in;j++){
            tmp=mult*i+buf_in[j];
            res=res_in[j];
            res1=(tmp-res)%(div);
            if(res1){
                res1=div-res1;
            }
            if(res1<max-count){
                buf_out[k]=tmp;
                res_out[k]=res1;
                k++; 
            }
                  
        }
    //}
    return k; 
}
int gen_next(int max,int count,int buf_in[8000],int res_in[8000],int num_in,int buf_out[8000],int res_out[8000]){
    int i,j;
    int k=0;
    int tmp;
    int res;
    int res1;
    static int mult;

    if (count==0) mult=1;
    else mult*=2*max-count+1;
    //printf("nult=%d\n",mult);
    for(i=0;i<max*2-count;i++){
        for(j=0;j<num_in;j++){
            tmp=mult*i+buf_in[j];
            res=res_in[j];
            res1=(tmp-res)%(max*2-count);
            if(res1){
                res1=max*2-count-res1;
            }
            if(res1<max-count){
                buf_out[k]=tmp;
                res_out[k]=res1;
                k++; 
            }
                  
        }
    }
    return k; 
}
int gen_next(int max){
    int i=max+1;
    int j=0;
    int last=0;
    int tmp;

    return j; 
}
int find_next(int max){
    if(max<5)ii++;
    else {
        ii++;
    }
    return ii;
}
int core(int max){
    int i,j;
    int res=max*2;
    int tootle;
    int tmp;
    ii=max+1;
    int sum=0;
    int ans[]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,13482720,25779600,68468401,610346880};

    int num_in;
    int num_out;
    num_in=1;
    buf0[0]=0;
    res0[0]=0;
    int *buf_in;
    int *buf_out;
    int *buf_tmp;
    int *res_in;
    int *res_out;
    int *res_tmp;
    buf_in=buf0;
    buf_out=buf1;
    res_in=res0;
    res_out=res1;
    num_out=gen_next(max,0,buf_in,res_in,num_in,buf_out,res_out);
    if(max==1){
        if(num_out<2)   return max*2;
        else return buf_out[1];
    }
    buf_tmp=buf_in;
    buf_in=buf_out;
    buf_out=buf_tmp;
    res_tmp=res_in;
    res_in=res_out;
    res_out=res_tmp;
    num_in=num_out;
    num_out=gen_next(max,1,buf_in,res_in,num_in,buf_out,res_out);
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", buf_out[i]);
    //}
    //printf("\n");
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", res_out[i]);
    //}
    //printf("\n");
    //printf("num=%d\n",num_out);
    if(max==2){
        for(i=1;i<num_out;i++)
            if(res_out[i]==0)
                return buf_out[i];
    }
    buf_tmp=buf_in;
    buf_in=buf_out;
    buf_out=buf_tmp;
    res_tmp=res_in;
    res_in=res_out;
    res_out=res_tmp;
    num_in=num_out;
    num_out=gen_next(max,2,buf_in,res_in,num_in,buf_out,res_out);
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", buf_out[i]);
    //}
    //printf("\n");
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", res_out[i]);
    //}
    //printf("\n");
    //printf("num=%d\n",num_out);
    if(max==3){
        for(i=1;i<num_out;i++)
            if(res_out[i]==0)
                return buf_out[i];
    }
    buf_tmp=buf_in;
    buf_in=buf_out;
    buf_out=buf_tmp;
    res_tmp=res_in;
    res_in=res_out;
    res_out=res_tmp;
    num_in=num_out;
    num_out=gen_next(max,3,buf_in,res_in,num_in,buf_out,res_out);
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", buf_out[i]);
    //}
    //printf("\n");
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", res_out[i]);
    //}
    //printf("\n");
    //printf("num=%d\n",num_out);
    if(max==4){
        for(i=1;i<num_out;i++)
            if(res_out[i]==0)
                return buf_out[i];
    }
    buf_tmp=buf_in;
    buf_in=buf_out;
    buf_out=buf_tmp;
    res_tmp=res_in;
    res_in=res_out;
    res_out=res_tmp;
    num_in=num_out;
    num_out=find_next(max,4,buf_in,res_in,num_in,buf_out,res_out);
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", buf_out[i]);
    //}
    //printf("\n");
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", res_out[i]);
    //}
    //printf("\n");
    //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
    if(max==5){
        for(i=1;i<num_out;i++)
            if(res_out[i]==0)
                return buf_out[i];
    }
    buf_tmp=buf_in;
    buf_in=buf_out;
    buf_out=buf_tmp;
    res_tmp=res_in;
    res_in=res_out;
    res_out=res_tmp;
    num_in=num_out;
    num_out=find_next(max,5,buf_in,res_in,num_in,buf_out,res_out);
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", buf_out[i]);
    //}
    //printf("\n");
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", res_out[i]);
    //}
    //printf("\n");
    //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
    if(max==6){
        for(i=1;i<num_out;i++)
            if(res_out[i]==0)
                return buf_out[i];
    }
    buf_tmp=buf_in;
    buf_in=buf_out;
    buf_out=buf_tmp;
    res_tmp=res_in;
    res_in=res_out;
    res_out=res_tmp;
    num_in=num_out;
    num_out=find_next(max,6,buf_in,res_in,num_in,buf_out,res_out);
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", buf_out[i]);
    //}
    //printf("\n");
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", res_out[i]);
    //}
    //printf("\n");
    //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
    if(max==7){
        for(i=1;i<num_out;i++)
            if(res_out[i]==0)
                return buf_out[i];
    }
    buf_tmp=buf_in;
    buf_in=buf_out;
    buf_out=buf_tmp;
    res_tmp=res_in;
    res_in=res_out;
    res_out=res_tmp;
    num_in=num_out;
    num_out=find_next(max,7,buf_in,res_in,num_in,buf_out,res_out);
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", buf_out[i]);
    //}
    //printf("\n");
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", res_out[i]);
    //}
    //printf("\n");
    //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
    if(max==8){
        for(i=1;i<num_out;i++)
            if(res_out[i]==0)
                return buf_out[i];
    }
    buf_tmp=buf_in;
    buf_in=buf_out;
    buf_out=buf_tmp;
    res_tmp=res_in;
    res_in=res_out;
    res_out=res_tmp;
    num_in=num_out;
    num_out=find_next(max,8,buf_in,res_in,num_in,buf_out,res_out);
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", buf_out[i]);
    //}
    //printf("\n");
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", res_out[i]);
    //}
    //printf("\n");
    //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
    if(max==9){
        for(i=1;i<num_out;i++)
            if(res_out[i]==0)
                return buf_out[i];
    }
    buf_tmp=buf_in;
    buf_in=buf_out;
    buf_out=buf_tmp;
    res_tmp=res_in;
    res_in=res_out;
    res_out=res_tmp;
    num_in=num_out;
    num_out=find_next(max,9,buf_in,res_in,num_in,buf_out,res_out);
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", buf_out[i]);
    //}
    //printf("\n");
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", res_out[i]);
    //}
    //printf("\n");
    //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
    if(max==10){
        for(i=1;i<num_out;i++)
            if(res_out[i]==0)
                return buf_out[i];
    }
    buf_tmp=buf_in;
    buf_in=buf_out;
    buf_out=buf_tmp;
    res_tmp=res_in;
    res_in=res_out;
    res_out=res_tmp;
    num_in=num_out;
    num_out=find_next(max,10,buf_in,res_in,num_in,buf_out,res_out);
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", buf_out[i]);
    //}
    //printf("\n");
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", res_out[i]);
    //}
    //printf("\n");
    //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
    if(max==11){
        for(i=1;i<num_out;i++)
            if(res_out[i]==0)
                return buf_out[i];
    }
    buf_tmp=buf_in;
    buf_in=buf_out;
    buf_out=buf_tmp;
    res_tmp=res_in;
    res_in=res_out;
    res_out=res_tmp;
    num_in=num_out;
    num_out=find_next(max,11,buf_in,res_in,num_in,buf_out,res_out);
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", buf_out[i]);
    //}
    //printf("\n");
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", res_out[i]);
    //}
    //printf("\n");
    //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
    if(max==12){
        for(i=1;i<num_out;i++)
            if(res_out[i]==0)
                return buf_out[i];
    }
    buf_tmp=buf_in;
    buf_in=buf_out;
    buf_out=buf_tmp;
    res_tmp=res_in;
    res_in=res_out;
    res_out=res_tmp;
    num_in=num_out;
    num_out=find_next(max,12,buf_in,res_in,num_in,buf_out,res_out);
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", buf_out[i]);
    //}
    //printf("\n");
    //for(i=0;i<num_out;i++){
    //    printf("%4d,", res_out[i]);
    //}
    //printf("\n");
    //printf("num=%d,max=%d\n",num_out,buf_out[num_out-1]);
    if(max==13){
        for(i=1;i<num_out;i++)
            if(res_out[i]==0)
                return buf_out[i];
    }
        return ans[max];
}
/*
    int buf[15][800000];
    int res[15][800000];
    int num[15];
    int last_num[15];
    int r_num[15];
    int mult_ram[15];
    int offset_ram[15];
    int count_ram[15];
    int offset[15];
int core1(int max){
    int i,j;
    int tmp;
    unsigned int mult=1;
    int nex;
    int res0,res1;
    for(j=0;j<15;j++){
        num[j]=0;
        last_num[j]=0;
        r_num[j]=0;
        mult_ram[j]=0;
        offset_ram[j]=0;
        count_ram[j]=0;
        offset[j]=0;

    }
    buf[0][0]=0;
    res[0][0]=0;
    num[0]=1;
    last_num[0]=1;
    mult_ram[0]=1;
    offset_ram[0]=0;
    count_ram[0]=0;
    for(j=0;j<max;j++){
        mult*=2*max-j;
        if(mult>1<<26) mult=1<<26;
        mult_ram[j+1]=mult;
        num[j+1]=0;
        last_num[j+1]=800000;
        offset_ram[j+1]=0;
        count_ram[j+1]=0;
    }
    
    for(i=0;i<1<<30;i=nex){
        nex=-1;
        res0=0;
        //printf("x%d,",i);
        if(i<mult_ram[1]){
            for(j=0;j<max;j++){
                int tmp=max*2-j;
                res1=(i-res0)%(tmp);
                if(res1){
                    res0=tmp-res1;
                }
                else 
                    res0=res1;
                if(res0<max-j){
                    buf[j+1][num[j+1]]=i;
                    res[j+1][num[j+1]]=res0;
                    num[j+1]++;
                    if(num[max]==2) {
                        //for(int k=0;k<num[0];k++)printf("%d,",buf[0][k]);printf("\n");
                        //for(int k=0;k<num[1];k++)printf("%d,",buf[1][k]);printf("\n");
                        //for(int k=0;k<num[2];k++)printf("%d,",buf[2][k]);printf("\n");
                        //for(int k=0;k<num[3];k++)printf("%d,",buf[3][k]);printf("\n");
                        return i; 
                    }
                }
                else
                    break;
            }
            nex=i+1;
            //printf("a%d,",nex);
            offset_ram[1]=0;
            count_ram[1]=1;
        }
        else if(i<mult_ram[2]){
            res0=res[1][offset_ram[1]++];
            for(j=1;j<max;j++){
                int tmp=max*2-j;
                res1=(i-res0)%(max*2-j);
                if(res1){
                    res0=max*2-j-res1;
                }
                else 
                    res0=res1;
                if(res0<max-j){
                    buf[j+1][num[j+1]]=i;
                    res[j+1][num[j+1]]=res0;
                    num[j+1]++; 
                    if(num[max]==2) {
                        //for(int k=0;k<num[0];k++)printf("%d,",buf[0][k]);printf("\n");
                        //for(int k=0;k<num[1];k++)printf("%d,",buf[1][k]);printf("\n");
                        //for(int k=0;k<num[2];k++)printf("%d,",buf[2][k]);printf("\n");
                        //for(int k=0;k<num[3];k++)printf("%d,",buf[3][k]);printf("\n");
                        //for(int k=0;k<num[4];k++)printf("%d,",buf[4][k]);printf("\n");
                        return i; 
                    }
                }
                else
                    break;
            }
            if(offset_ram[1]==num[1]){
                offset_ram[1]=0;
                count_ram[1]++;
            }

                
            nex=count_ram[1]*mult_ram[1]+buf[1][offset_ram[1]];
            offset_ram[2]=0;
            count_ram[2]=1;
            //printf("b%d,",nex);
        }
        else if(i<mult_ram[3]){
            res0=res[2][offset_ram[2]++];
            for(j=2;j<max;j++){
                int tmp=max*2-j;
                res1=(i-res0)%(tmp);
                if(res1){
                    res0=tmp-res1;
                }
                else 
                    res0=res1;
                if(res0<max-j){
                    buf[j+1][num[j+1]]=i;
                    res[j+1][num[j+1]]=res0;
                    num[j+1]++; 
                    if(num[max]==2) {
                        //for(int k=0;k<num[0];k++)printf("%d,",buf[0][k]);printf("\n");
                        //for(int k=0;k<num[1];k++)printf("%d,",buf[1][k]);printf("\n");
                        //for(int k=0;k<num[2];k++)printf("%d,",buf[2][k]);printf("\n");
                        //for(int k=0;k<num[3];k++)printf("%d,",buf[3][k]);printf("\n");
                        //for(int k=0;k<num[4];k++)printf("%d,",buf[4][k]);printf("\n");
                        //for(int k=0;k<num[5];k++)printf("%d,",buf[5][k]);printf("\n");
                        return i; 
                    }
                }
                else
                    break;
            }
            if(offset_ram[2]==num[2]){
                offset_ram[2]=0;
                count_ram[2]++;
            }

                
            nex=count_ram[2]*mult_ram[2]+buf[2][offset_ram[2]];
            offset_ram[3]=0;
            count_ram[3]=1;
            //printf("c%d,",nex);
        }
        else if(i<mult_ram[4]){
            res0=res[3][offset_ram[3]++];
            for(j=3;j<max;j++){
                int tmp=max*2-j;
                res1=(i-res0)%(tmp);
                if(res1){
                    res0=tmp-res1;
                }
                else 
                    res0=res1;
                if(res0<max-j){
                    buf[j+1][num[j+1]]=i;
                    res[j+1][num[j+1]]=res0;
                    num[j+1]++; 
                    if(num[max]==2) {
                        //for(int k=0;k<num[0];k++)printf("%d,",buf[0][k]);printf("\n");
                        //for(int k=0;k<num[1];k++)printf("%d,",buf[1][k]);printf("\n");
                        //for(int k=0;k<num[2];k++)printf("%d,",buf[2][k]);printf("\n");
                        //for(int k=0;k<num[3];k++)printf("%d,",buf[3][k]);printf("\n");
                        //for(int k=0;k<num[4];k++)printf("%d,",buf[4][k]);printf("\n");
                        //for(int k=0;k<num[5];k++)printf("%d,",buf[5][k]);printf("\n");
                        //for(int k=0;k<num[6];k++)printf("%d,",buf[6][k]);printf("\n");
                        return i; 
                    }
                }
                else
                    break;
            }
            if(offset_ram[3]==num[3]){
                offset_ram[3]=0;
                count_ram[3]++;
            }

                
            nex=count_ram[3]*mult_ram[3]+buf[3][offset_ram[3]];
            offset_ram[4]=0;
            count_ram[4]=1;
            //printf("d%d,",nex);
        }
        else if(i<mult_ram[5]){
            res0=res[4][offset_ram[4]++];
            for(j=4;j<max;j++){
                int tmp=max*2-j;
                res1=(i-res0)%(tmp);
                if(res1){
                    res0=tmp-res1;
                }
                else 
                    res0=res1;
                if(res0<max-j){
                    buf[j+1][num[j+1]]=i;
                    res[j+1][num[j+1]]=res0;
                    num[j+1]++; 
                    if(num[max]==2) {
                        //for(int k=0;k<num[0];k++)printf("%d,",buf[0][k]);printf("\n");
                        //for(int k=0;k<num[1];k++)printf("%d,",buf[1][k]);printf("\n");
                        //for(int k=0;k<num[2];k++)printf("%d,",buf[2][k]);printf("\n");
                        //for(int k=0;k<num[3];k++)printf("%d,",buf[3][k]);printf("\n");
                        //for(int k=0;k<num[4];k++)printf("%d,",buf[4][k]);printf("\n");
                        //for(int k=0;k<num[5];k++)printf("%d,",buf[5][k]);printf("\n");
                        //for(int k=0;k<num[6];k++)printf("%d,",buf[6][k]);printf("\n");
                        return i; 
                    }
                }
                else
                    break;
            }
            if(offset_ram[4]==num[4]){
                offset_ram[4]=0;
                count_ram[4]++;
            }

                
            nex=count_ram[4]*mult_ram[4]+buf[4][offset_ram[4]];
            offset_ram[5]=0;
            count_ram[5]=1;
            //printf("d%d,",nex);
        }
        else if(i<mult_ram[6]){
            res0=res[5][offset_ram[5]++];
            for(j=5;j<max;j++){
                int tmp=max*2-j;
                res1=(i-res0)%(tmp);
                if(res1){
                    res0=tmp-res1;
                }
                else 
                    res0=res1;
                if(res0<max-j){
                    buf[j+1][num[j+1]]=i;
                    res[j+1][num[j+1]]=res0;
                    num[j+1]++; 
                    if(num[max]==2) {
                        //for(int k=0;k<num[0];k++)printf("%d,",buf[0][k]);printf("\n");
                        //for(int k=0;k<num[1];k++)printf("%d,",buf[1][k]);printf("\n");
                        //for(int k=0;k<num[2];k++)printf("%d,",buf[2][k]);printf("\n");
                        //for(int k=0;k<num[3];k++)printf("%d,",buf[3][k]);printf("\n");
                        //for(int k=0;k<num[4];k++)printf("%d,",buf[4][k]);printf("\n");
                        //for(int k=0;k<num[5];k++)printf("%d,",buf[5][k]);printf("\n");
                        //for(int k=0;k<num[6];k++)printf("%d,",buf[6][k]);printf("\n");

                        //for(int k=0;k<15;k++)printf("%d,",num[k]);printf("\n");
                        return i; 
                    }
                }
                else
                    break;
            }
            if(offset_ram[5]==num[5]){
                offset_ram[5]=0;
                count_ram[5]++;
            }

                
            nex=count_ram[5]*mult_ram[5]+buf[5][offset_ram[5]];
            offset_ram[6]=0;
            count_ram[6]=1;
            //printf("d%d,",nex);
        }
        else{
            break;
        }
    }
    //for(j=0;j<max+1;j++){
    //    for(i=0;i<num[j];i++){
    //        printf("%d,",buf[j][i]);
    //    }
    //    printf("\n");
    //}
    //for(i=0;i<15;i++)
    //    printf("%d,",num[i]);
    //printf("\n");
    return i;
}
*/

int main(){
    int max_p  ;
    int i;
    //tmp_buf0[0]=0;

    int tmp;
    int max;
    int a=scanf("%d",&max);
    int ans[]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,13482720,25779600,68468401,610346880};
    while(max){
        tmp=core(max);
        printf("%d\n",tmp);
        //input(tmp_buf,max);
        //maopao(tmp_buf,max);
        //i=core(tmp_buf,max);
        //printf("%d\n",i);
        a=scanf("%d",&max);
    }
    return 0;   
}

• Re:老老实实计算也能ac，只要发现周期性 (21908) 3187180646 2024-03-01 14:55:56