Description
lxhgww的小名叫“小L”,这是因为他总是很喜欢L型的东西。小L家的客厅是一个的矩形,现在他想用L型的地板来铺满整个客厅,客厅里有些位置有柱子,不能铺地板。现在小L想知道,用L型的地板铺满整个客厅有多少种不同的方案?
需要注意的是,如下图所示,L型地板的两端长度可以任意变化,但不能长度为0。铺设完成后,客厅里面所有没有柱子的地方都必须铺上地板,但同一个地方不能被铺多次。
Input
输入的第一行包含两个整数,R和C,表示客厅的大小。
接着是R行,每行C个字符。’_’表示对应的位置是空的,必须铺地板;’*’表示对应的位置有柱子,不能铺地板。
Output
输出一行,包含一个整数,表示铺满整个客厅的方案数。由于这个数可能很大,只需输出它除以20110520的余数。
Sample Input
2 2
*_
__
*_
__
Sample Output
1
HINT
R*C<=100
正解:插头$dp$。
插头$dp$第一题,写了巨久。。
这道题还是比较裸的,我们把轮廓线的状态分为$3$种情况,没有插头,插头没拐弯,插头已经拐过弯了,然后就很好转移了。
在每一行的最后一个格子转移的时候要特判。轮廓线到下一行要左移一位。注意用$4$进制比$3$进制常数更小,$4$进制状态较大,所以要手写$hash$。
#include <bits/stdc++.h>
#define ll long long
#define RG register
#define il inline
#define M (1<<22)
#define rhl (20110520)
#define w(s,p) ((s)>>((p)<<1)&3)
#define upd(s,p,v) ((s)^(w(s,p)<<((p)<<1))^((v)<<((p)<<1))) using namespace std; int vis[M],S[][M],f[][M],sz[M],g[][],n,m,pre,cur,ans; il char gc(){
RG char ch=getchar();
while (ch!='*' && ch!='_') ch=getchar(); return ch;
} il void add(RG int s,RG int v){
if (vis[s]){
f[cur][vis[s]]+=v;
if (f[cur][vis[s]]>=rhl) f[cur][vis[s]]-=rhl;
return;
}
vis[s]=++sz[cur],S[cur][sz[cur]]=s,f[cur][sz[cur]]=v; return;
} int main(){
#ifndef ONLINE_JUDGE
freopen("floor.in","r",stdin);
freopen("floor.out","w",stdout);
#endif
cin>>n>>m;
for (RG int i=;i<=n;++i)
for (RG int j=;j<=m;++j)
if (n>=m) g[i][j]=gc()=='_'; else g[j][i]=gc()=='_';
if (n<m) swap(n,m); sz[]=f[][]=;
for (RG int i=;i<=n;++i){
for (RG int k=;k<=sz[cur];++k) (S[cur][k]<<=)&=(<<((m+)<<))-;
for (RG int j=;j<=m;++j){
pre=cur,sz[cur^=]=;
if (!g[i][j]){
for (RG int k=;k<=sz[pre];++k)
if (!w(S[pre][k],j-) && !w(S[pre][k],j) && f[pre][k]) add(S[pre][k],f[pre][k]);
for (RG int k=;k<=sz[cur];++k) vis[S[cur][k]]=; continue;
}
for (RG int k=,x,y,s,v;k<=sz[pre];++k){
s=S[pre][k],v=f[pre][k]; if (!v) continue;
x=w(s,j-),y=w(s,j);
if (!x && !y){
if (g[i][j+]) add(upd(upd(s,j-,),j,),v);
if (g[i+][j]) add(upd(upd(s,j-,),j,),v);
if (g[i][j+] && g[i+][j]) add(upd(upd(s,j-,),j,),v);
}
if (!x && y==){
if (g[i+][j]) add(upd(upd(s,j-,),j,),v);
if (g[i][j+]) add(upd(upd(s,j-,),j,),v);
}
if (x== && !y){
if (g[i][j+]) add(upd(upd(s,j-,),j,),v);
if (g[i+][j]) add(upd(upd(s,j-,),j,),v);
}
if (!x && y==){
add(upd(upd(s,j-,),j,),v);
if (g[i+][j]) add(upd(upd(s,j-,),j,),v);
}
if (x== && !y){
add(upd(upd(s,j-,),j,),v);
if (g[i][j+]) add(upd(upd(s,j-,),j,),v);
}
if (x== && y==) add(upd(upd(s,j-,),j,),v);
}
for (RG int k=;k<=sz[cur];++k) vis[S[cur][k]]=;
}
}
for (RG int i=;i<=sz[cur];++i) if (!S[cur][i]) ans=f[cur][i];
cout<<ans; return ;
}