感谢大佬的教导->

容易注意到，本题的合法路径“L型地板”有一些特殊的地方：拐弯且仅拐弯一次。

这由于一条路径只有两种状态：拐弯过和没拐弯过，因此我们可以尝试着这样定义新的插头：

我们使用三进制，0代表没有插头，1代表没拐弯过的路径，2代表已经拐弯过的路径。

依然设当前转移到格子(x,y)，设y-1号插头状态为p1，y号插头状态为p2。

那么会有下面的几种情况：

　　情况1：p1==0&&p2==0

　　　　这时我们有三种可选的策略：

　　　　　　①以当前位置为起点，从p1方向引出一条新的路径（把p1修改为1号插头）

　　　　　　②以当前位置为起点，从p2方向引出一条新的路径（把p2修改为1号插头）

　　　　　　③以当前位置为“L”型路径的转折点，向p1，p2两个方向均引出一个2号插头.

　　情况2：p1==0&&p2==1

　　　　由于p2节点还没有拐过弯，因此我们有2种可选的策略：

　　　　　　①继续直走，不拐弯，即上->下（把p1修改为1号插头，p2置0）

　　　　　　②选择拐弯，即上->右（把p2改为2号插头）

　　情况3：p1==1&&p2==0

　　　　这种情况和情况2类似

　　情况4：p1==0&&p2==2

　　　　由于p2节点已经拐过弯，所以我们有如下的两种策略：

　　　　①路径在此停止。那么我们以本格作为L型路径的一个端点。如果当前处于最后一个非障碍格子，如果没有其他的插头，我们此时就可以统计答案了。

　　　　②路径延续。由于p2已经转弯过，因此我们只能选择继续直走，即上->下（把p1修改为2号插头，p2置0）和之前相似的方法把独立插头传递下去即可。

　　情况5：p1==2&&p2==0

　　　　这种情况与情况4类似

　　情况6：p1==1&&p2==1

　　　　这种情况下，两块地板均没有拐过弯，因此我们可以在本格将这两块地板合并，形成一个合法的“L”型路径，并将本格看做他们的转折点。（把p1和p2都置为0）

至此，新插头定义的状态转移已经讨论完成。

不难发现，这种新的插头定义可以处理可能发生的所有可行情况。

然后上代码

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 using namespace std; 6 const int N=105,HASH=200097,mod=20110520; 7 int ans,n,m,lastx,lasty;char c[N][N];bool room[N][N]; 8 struct node{ 9     int val[HASH],key[HASH],Hash[HASH],sz;10     inline void init(){11         memset(val,0,sizeof(val)),memset(Hash,0,sizeof(Hash));12         memset(key,-1,sizeof(key)),sz=0;13     }14     inline void newhash(int id,int state){Hash[id]=++sz,key[sz]=state;}15     inline int &operator [](const int state){16         for(int i=state%HASH;;i=(i+1==HASH)?0:i+1){17             if(!Hash[i]) newhash(i,state);18             if(key[Hash[i]]==state) return val[Hash[i]];19         }20     }21 }f[2];22 inline int find(int state,int pos){
   return (state>>((pos-1)<<1))&3;}23 inline void set(int &state,int pos,int val){24     pos=(pos-1)<<1,state|=3<
        
         <
         
          <
          
           n){78 for(int i=1;i<=n;++i)79 for(int j=i+1;j<=m;++j)80 swap(room[i][j],room[j][i]);81 swap(n,m);82 }83 int flag=1;84 for(int i=n;i&&flag;--i)85 for(int j=m;j&&flag;--j)86 if(room[i][j]){lastx=i,lasty=j;flag=0;}87 f[0].init(),f[0][0]=1;88 for(int i=1;i<=n;++i){89 for(int j=1;j<=m;++j) solve(i,j);90 if(i!=n)91 for(int j=1,last=(i*m)&1,tot=f[last].sz;j<=tot;++j)92 f[last].key[j]<<=2;93 }94 printf("%d\n",ans);95 return 0;96 }