自动搬运

查看原文

来自洛谷，原作者为

	zxh_qwq & clouds_ink & Aurora_Crystal|| 可以简称 zxh || ENTP-A || 互关请先看专栏互关条件

搬运于2025-08-24 21:18:28，当前版本为作者最后更新于2025-07-30 15:18:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

B4299 题解

第一次写黑题题解。

思路

我们观察后可以发现，这其实就是一个插头 DP 的模板。

特别注意到，因为一条回路正着走和反着走是不一样的两条路线，因此最后要把回路数乘 $2$。

代码

#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
typedef long long LL;
const LL maxn=13;
const LL hs=299987;
LL n,m,ex,ey,now,last,ans;
LL a[maxn][maxn],head[300000],next[2<<24],que[2][2<<24],val[2][2<<24],cnt[2],inc[13];
inline void init(){
   scanf("%lld%lld",&n,&m);
   for(LL i=1;i<=n;++i){
       char s[100];
       for(LL j=1;j<=m;++j){
           a[i][j]=1;
       }
   }
           ex=n; ey=m;
   inc[0]=1;
   for(LL i=1;i<=13;++i)
       inc[i]=inc[i-1]<<2;
}
inline void insert(LL bit,LL num){
   LL u=bit%hs+1;
   for(LL i=head[u];i;i=next[i]){
       if(que[now][i]==bit){
           val[now][i]+=num;
           return;
       }
   }
   next[++cnt[now]]=head[u];
   head[u]=cnt[now];
   que[now][cnt[now]]=bit;
   val[now][cnt[now]]=num;
}
inline void work(){
   cnt[now]=1; val[now][1]=1; que[now][1]=0;
   for(LL i=1;i<=n;++i){
       for(LL j=1;j<=cnt[now];++j)
           que[now][j]<<=2;
       for(LL j=1;j<=m;++j){
           memset(head,0,sizeof(head));
           last=now; now^=1;
           cnt[now]=0;
           for(LL k=1;k<=cnt[last];++k){
               LL bit=que[last][k],num=val[last][k];
               LL b1=(bit>>((j-1)*2))%4,b2=(bit>>(j*2))%4;
               if(!a[i][j]){
                   if(!b1&&!b2)
                       insert(bit,num);
               }else if(!b1&&!b2){
                   if(a[i+1][j]&&a[i][j+1])
                       insert(bit+inc[j-1]+inc[j]*2,num);
               }else if(!b1&&b2){
                   if(a[i][j+1])
                       insert(bit,num);
                   if(a[i+1][j])
                       insert(bit-inc[j]*b2+inc[j-1]*b2,num);
               }else if(b1&&!b2){
                   if(a[i+1][j])
                       insert(bit,num);
                   if(a[i][j+1])
                       insert(bit-inc[j-1]*b1+inc[j]*b1,num);
               }else if(b1==1&&b2==1){
                   LL k1=1;
                   for(LL l=j+1;l<=m;++l){
                       if((bit>>(l*2))%4==1)
                           ++k1;
                       if((bit>>(l*2))%4==2)
                           --k1;
                       if(!k1){
                           insert(bit-inc[j]-inc[j-1]-inc[l],num);
                           break;
                       }
                   }
               }else if(b1==2&&b2==2){
                   LL k1=1;
                   for(LL l=j-2;l>=0;--l){
                       if((bit>>(l*2))%4==1)
                           --k1;
                       if((bit>>(l*2))%4==2)
                           ++k1;
                       if(!k1){
                           insert(bit-inc[j]*2-inc[j-1]*2+inc[l],num);
                           break;
                       }
                   }
               }else if(b1==2&&b2==1){
                   insert(bit-inc[j-1]*2-inc[j],num);
               }else if(i==ex&&j==ey){
                   ans+=num;
               }
           }
       }
   }
}
main(){
   init();
   work();
   printf("%lld",ans*2);
   return 0;
}