题目大意：给一个网格，有些网格有障碍，问有多少条哈密顿回路。

——————————————————-

插头dp模板题，详见：

参考代码和思路于：

 

#include
     
      #include
      
       using namespace std;typedef long long ll;const int INF=2147483647;const int mod=300000;const int M=300005;struct node{    int to,nxt;}edge[M];int head[M],cnt;int n,m,e1,e2;bool mp[15][15]; //记录是否有障碍 int cur,pre;  //滚动数组 int state[2][M];  //记录状态,滚动 ll ans[2][M],cntt; //记录答案 int tot[2]; //记录状态总数 int bit[20];  //提取状态使用 inline void getbit(){    for(int i=1;i<15;i++)bit[i]=i<<1;    return;}inline void add(int u,int v){    cnt++;    edge[cnt].to=v;    edge[cnt].nxt=head[u];    head[u]=cnt;    return;}void insert(int now,ll num){    int u=now%mod;    for(int i=head[u];i;i=edge[i].nxt){    int v=edge[i].to;    if(state[cur][v]==now){        ans[cur][v]+=num;        return;    }    }    add(u,++tot[cur]);    state[cur][tot[cur]]=now;    ans[cur][tot[cur]]=num;    return;}void plugdp(){    cur=0;    tot[cur]=1;    ans[cur][1]=1;    state[cur][1]=0;    for(int i=1;i<=n;i++){    for(int j=1;j<=tot[cur];j++){        state[cur][j]<<=2;    }    for(int j=1;j<=m;j++){        memset(head,0,sizeof(head));cnt=0;        pre=cur,cur^=1;        tot[cur]=0;        for(int k=1;k<=tot[pre];k++){        int now=state[pre][k];        ll num=ans[pre][k];        int is_down=(now>>bit[j-1])%4;        int is_right=(now>>bit[j])%4;        if(!mp[i][j]){            if(!is_down&&!is_right)            insert(now,num);        }        else if(!is_down&&!is_right){            if(mp[i][j+1]&&mp[i+1][j])            insert(now+(1<
       
        <
        
         >bit[l])%4==1)count++;            if((now>>bit[l])%4==2)count--;            if(!count){                insert(now-(1<
         
          <
          
           <
           
            =0;l--){ if((now>>bit[l])%4==1) count--; if((now>>bit[l])%4==2) count++; if(!count){ insert(now+(1<
            
             <
             
              <