bzoj2331 [SCOI2011]地板

Description

lxhgww的小名叫“小L”，这是因为他总是很喜欢L型的东西。小L家的客厅是一个的矩形，现在他想用L型的地板来铺满整个客厅，客厅里有些位置有柱子，不能铺地板。现在小L想知道，用L型的地板铺满整个客厅有多少种不同的方案？

需要注意的是，如下图所示，L型地板的两端长度可以任意变化，但不能长度为0。铺设完成后，客厅里面所有没有柱子的地方都必须铺上地板，但同一个地方不能被铺多次。

Input

输入的第一行包含两个整数，R和C，表示客厅的大小。

接着是R行，每行C个字符。’_’表示对应的位置是空的，必须铺地板；’*’表示对应的位置有柱子，不能铺地板。

Output

输出一行，包含一个整数，表示铺满整个客厅的方案数。由于这个数可能很大，只需输出它除以20110520的余数。

Sample Input

2 2
*_
__

Sample Output

HINT

R*C<=100

正解：插头$dp$。

插头$dp$第一题，写了巨久。。

这道题还是比较裸的，我们把轮廓线的状态分为$3$种情况，没有插头，插头没拐弯，插头已经拐过弯了，然后就很好转移了。

在每一行的最后一个格子转移的时候要特判。轮廓线到下一行要左移一位。注意用$4$进制比$3$进制常数更小，$4$进制状态较大，所以要手写$hash$。

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 #define RG register
 4 #define il inline
 5 #define M (1<<22)
 6 #define rhl (20110520)
 7 #define w(s,p) ((s)>>((p)<<1)&3)
 8 #define upd(s,p,v) ((s)^(w(s,p)<<((p)<<1))^((v)<<((p)<<1)))
 9 
10 using namespace std;
11 
12 int vis[M],S[2][M],f[2][M],sz[M],g[110][110],n,m,pre,cur,ans;
13 
14 il char gc(){
15   RG char ch=getchar();
16   while (ch!='*' && ch!='_') ch=getchar(); return ch;
17 }
18 
19 il void add(RG int s,RG int v){
20   if (vis[s]){
21     f[cur][vis[s]]+=v;
22     if (f[cur][vis[s]]>=rhl) f[cur][vis[s]]-=rhl;
23     return;
24   }
25   vis[s]=++sz[cur],S[cur][sz[cur]]=s,f[cur][sz[cur]]=v; return;
26 }
27 
28 int main(){
29 #ifndef ONLINE_JUDGE
30   freopen("floor.in","r",stdin);
31   freopen("floor.out","w",stdout);
32 #endif
33   cin>>n>>m;
34   for (RG int i=1;i<=n;++i)
35     for (RG int j=1;j<=m;++j)
36       if (n>=m) g[i][j]=gc()=='_'; else g[j][i]=gc()=='_';
37   if (n<m) swap(n,m); sz[0]=f[0][1]=1;
38   for (RG int i=1;i<=n;++i){
39     for (RG int k=1;k<=sz[cur];++k) (S[cur][k]<<=2)&=(1<<((m+1)<<1))-1;
40     for (RG int j=1;j<=m;++j){
41       pre=cur,sz[cur^=1]=0;
42       if (!g[i][j]){
43     for (RG int k=1;k<=sz[pre];++k)
44       if (!w(S[pre][k],j-1) && !w(S[pre][k],j) && f[pre][k]) add(S[pre][k],f[pre][k]);
45     for (RG int k=1;k<=sz[cur];++k) vis[S[cur][k]]=0; continue;
46       }
47       for (RG int k=1,x,y,s,v;k<=sz[pre];++k){
48     s=S[pre][k],v=f[pre][k]; if (!v) continue;
49     x=w(s,j-1),y=w(s,j);
50     if (!x && !y){
51       if (g[i][j+1]) add(upd(upd(s,j-1,0),j,1),v);
52       if (g[i+1][j]) add(upd(upd(s,j-1,1),j,0),v);
53       if (g[i][j+1] && g[i+1][j]) add(upd(upd(s,j-1,2),j,2),v);
54     }
55     if (!x && y==1){
56       if (g[i+1][j]) add(upd(upd(s,j-1,1),j,0),v);
57       if (g[i][j+1]) add(upd(upd(s,j-1,0),j,2),v);
58     }
59     if (x==1 && !y){
60       if (g[i][j+1]) add(upd(upd(s,j-1,0),j,1),v);
61       if (g[i+1][j]) add(upd(upd(s,j-1,2),j,0),v);
62     }
63     if (!x && y==2){
64       add(upd(upd(s,j-1,0),j,0),v);
65       if (g[i+1][j]) add(upd(upd(s,j-1,2),j,0),v);
66     }
67     if (x==2 && !y){
68       add(upd(upd(s,j-1,0),j,0),v);
69       if (g[i][j+1]) add(upd(upd(s,j-1,0),j,2),v);
70     }
71     if (x==1 && y==1) add(upd(upd(s,j-1,0),j,0),v);
72       }
73       for (RG int k=1;k<=sz[cur];++k) vis[S[cur][k]]=0;
74     }
75   }
76   for (RG int i=1;i<=sz[cur];++i) if (!S[cur][i]) ans=f[cur][i];
77   cout<<ans; return 0;
78 }