#include #include #include using namespace std; #define LL long long LL dp[2][1<<24];//记录方案数 int state[2][1<<24];//记录状态,S=state[pre][s],pre为前一个格子标记,s为状态编号,S为状态 int total[2];//记录状态总数 int pre,now; int endx,endy;//记录最后一个非障碍格子 bool map[15][15]; int m,n; LL ans; const int HASH=40001;//坑点!!哈希值太小会超时!4位素数超时,m<=12,用5位数素数,如30007 int Hash[HASH];//记录S对应的哈希值x的状态编号 void HashIn(int S,LL num){ int x=S%HASH; while(~Hash[x]&&state[now][Hash[x]]!=S){//线性探测 x++; x%=HASH; } if(Hash[x]==-1){//未找到,加入hash表中 dp[now][total[now]]=num; state[now][total[now]]=S; Hash[x]=total[now];//记录状态编号 total[now]++; } else//找到,累加方案数 dp[now][Hash[x]]+=num; } void init(){ memset(map,0,sizeof(map)); endx=-1; for(int i=0;i>(p*l))&((1<0)^(q>0)){//p、q有一个为0,第三种情况 if(map[i+(p>0)][j+(q>0)]) HashIn(S,num); if(map[i+(q>0)][j+(p>0)]){ int nS=S; setV(nS,j,q);//p、q交换 setV(nS,j+1,p); HashIn(nS,num); } continue; } if(p==1&&q==1){//第四种情况,4.1 int find=1; for(int v=j+2;v<=m;v++){//向后搜q匹配的右括号),改为左括号 int k=getV(S,v); if(k==1) find++; else if(k==2) find--; if(find==0){ int nS=S; setV(nS,j,0);//p、q置0 setV(nS,j+1,0); setV(nS,v,1);//改为左括号 HashIn(nS,num); break; } } continue; } if(p==2&&q==2){//第四种情况,4.2 int find=1; for(int v=j-1;v>=0;v--){//向前搜p匹配的左括号(,改为右括号 int k=getV(S,v); if(k==2) find++; else if(k==1) find--; if(find==0){ int nS=S; setV(nS,j,0);//p、q置0 setV(nS,j+1,0); setV(nS,v,2);//改为右括号 HashIn(nS,num); break; } } continue; } if(p==2&&q==1){//第四种情况,4.3 int nS=S; setV(nS,j,0);//p、q置0 setV(nS,j+1,0); HashIn(nS,num); continue; } if(p==1&&q==2){//第四种情况,4.4 if(i==endx&&j==endy)//最后一个非障碍格子 ans+=num; } } } swap(now,pre); } memsetnow();//哈希表清空 for(int s=0;s