[USACO 6.1.1 Postal Vans]高精度、找规律

【题目大意】找一个特殊图哈密顿回路的方案数。

【算法分析】

我先DFS了一下，感觉如果列是4的话，应该是一个4阶的递归式。

然后找到规律。。。OH,YEAH，AC

规律就是F[n]=2F[n-1]+2F[n-2]-2F[n-3]+F[n-4]

【其它】1A

【CODE】

/*
ID:jie22221
TASK:vans
LANG:C++
*/
#include #include const int M=100;
const int Mod=100000;
struct bigint{int d[M+1];};
int px[4]={-1,1,0,0},py[4]={0,0,1,-1};
int n,limit,total,ans;
bigint f[1001];
bool v[5][5];

void dfs(int x,int y){
    if (total==4*limit-1){
        if (x+y==3) ans++;
        return;
    }
    int k,tx,ty;
    v[x][y]=true;
    total++;
    for (k=0;k<4;k++){
        tx=x+px[k]; ty=y+py[k];
        if (tx<1 || tx>4 || ty<1 || ty>limit || v[tx][ty]) continue;
        dfs(tx,ty);
    }   
    v[x][y]=false;
    total–;
}   

bigint plus(bigint x,bigint y){
    for (int i=1;i<=M;i++) x.d[i]+=y.d[i];
    for (int i=M;i>=1;i–){
        x.d[i-1]+=x.d[i]/Mod;
        x.d[i]%=Mod;
    }   
    return x;
}

bigint dec(bigint x,bigint y){
    for (int i=1;i<=M;i++) x.d[i]-=y.d[i];
    for (int i=M;i>=1;i–)
      while (x.d[i]<0){
          x.d[i]+=Mod;
          x.d[i-1]–;
      }   
    return x;
}   

void init(){
    memset(f,0,sizeof(f));
    for (limit=1;limit<=4;limit++){
        ans=0;
        total=0;
        dfs(1,1);
        f[limit].d[M]=ans;
    }
}

void put(bigint x){
    int st;
    for (st=0;st<=M;st++)
      if (x.d[st]) break;
    printf("%d",x.d[st]);
    for (int i=st+1;i<=M;i++){
        int div=Mod/10,mod=Mod;
        while (div>0){
            printf("%d",x.d[i]%mod/div);
            mod/=10;
            div/=10;
        }   
    }   
    printf("n");
}   

void work(){
    scanf("%d",&n);
    if (n<=4){
        printf("%dn",f[n].d[M]);
        return;
    }
    bigint tmp;
    for (int i=5;i<=n;i++){
       memset(tmp.d,0,sizeof(tmp.d));
       tmp=plus(f[i-1],f[i-1]);
       f[i]=plus(f[i],tmp);
       tmp=plus(f[i-2],f[i-2]);
       f[i]=plus(f[i],tmp);
       tmp=plus(f[i-3],f[i-3]);
       f[i]=dec(f[i],tmp);
       f[i]=plus(f[i],f[i-4]);
    }
    put(f[n]);
}   

int main(){
    freopen("vans.in","r",stdin);
    freopen("vans.out","w",stdout);
    init();
    work();
}