插头DP
本题为CDQ《基于连通性状态压缩的动态规划的……（我忘了）》里的例题！（嗯就是这样……）
先膜拜一下ccy大神……http://blog.sina.com.cn/s/blog_51cea4040100gmky.html
在这里将我当初看插头DP的一些不解之处写出来，给大家提供一些参考：
以前我老是搞不懂“左/右插头”的区分……今天终于搞明白了：左插头是一个联通块与轮廓线的左边的交点，右插头是靠右的交点……这下那些分情况讨论的状态转移瞬间就明白了= =
然后是状态表示……其实以前用状压都是一位表示一个状态，而插头DP由于用的是3(4)进制，所以是二进制下的两位来表示一个插头的状态（两位的话就可以表示0/1/2了，一位只能表示0/1）
状态转移其实就是删掉/加上插头的操作……看了代码很好懂……sigh……当年是一看长代码就头晕，唉
其实我们是在对每一个格子枚举可行状态的……要不然怎么叫统计方案数啊= =（这一点我一开始真的没想到……so sad……too naive）
其实在看插头DP代码的过程中也顺便理解了Hash……原来hash向后排是这个意思，开个数组记录下每个hash值所对应的原值就好了，好像也没那么难的样子……为什么当初我NOIP的时候就没学会呢……
//Ural 1519
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define CC(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*=sign;
}
const int N=1e7+;
typedef long long LL;
typedef unsigned long long u64;
/******************tamplate*********************/
const int sz=;
bool mp[][];
int n,m,nn,mm,k;
int tot[],bit[],hash[sz],state[][sz];
u64 dp[][sz],ans;
void init(){
CC(mp,);
CC(dp,);
tot[]=dp[][]=,ans=k=;
state[][]=;
char ch;
F(i,,n){
scanf("%c",&ch);
F(j,,m){
scanf("%c",&ch);
mp[i][j]=ch=='.';
if (mp[i][j]) nn=i,mm=j;
}
}
}
void hash_in(int s,u64 sum){
int p=s%sz;
while(hash[p]){
if (state[k][hash[p]]==s){
dp[k][hash[p]]+=sum;
return;
}
p++;
if (p==sz) p=;
}
hash[p]=++tot[k];
state[k][hash[p]]=s;
dp[k][hash[p]]=sum;
}
#define in hash_in(s,sum)
void work(){
F(i,,n){
F(j,,m){
k^=;
tot[k]=;
CC(hash,);
F(u,,tot[-k]){
int s=state[-k][u];
u64 sum=dp[-k][u];
int p=(s>>bit[j-])&,q=(s>>bit[j])&;
if (!mp[i][j]){ if(!p && !q) in; }
else{
if (!p && !q){
if (!mp[i][j+]||!mp[i+][j]) continue;
s=s^(<<bit[j-])^(<<bit[j]<<),in;
}else if(!p && q){
if (mp[i][j+]) in;
if (mp[i+][j]) s=s^q*(<<bit[j-])^q*(<<bit[j]),in;
}else if(p && !q){
if (mp[i+][j]) in;
if (mp[i][j+]) s=s^p*(<<bit[j-])^p*(<<bit[j]),in;
}else if(p+q==){
int nd=;
F(u,j+,m){
int w=(s>>bit[u])&;
if (w==) nd++;
if (w==) nd--;
if (!nd) {s-=(<<bit[u]); break;}//这两个地方不能将+/-改成^
//废话！因为这里是把右插头（2）改成左插头（1）了！用异或就把2改成3了……那算神马……
}
s=s^(<<bit[j])^(<<bit[j-]),in;
}else if(p+q==){
int nd=;
D(u,j-,){
int w=(s>>bit[u])&;
if (w==) nd++;
if (w==) nd--;
if (!nd) {s+=(<<bit[u]); break;}//这里是将左插头（1）改成右插头（2）
}
s=s^(<<bit[j]<<)^(<<bit[j-]<<),in;
}else if(p== && q==){
if (i==nn && j==mm) ans+=sum;
}else if(p== && q==) s=s^(<<bit[j-]<<)^(<<bit[j]),in;
}
}
}
F(j,,tot[k]) state[k][j]<<=;
}
printf("%llu\n",ans);
} int main(){
#ifndef ONLINE_JUDGE
freopen("1519.in","r",stdin);
freopen("1519.out","w",stdout);
#endif
F(i,,) bit[i]=i<<;
while(scanf("%d%d",&n,&m)!=EOF){
init();
work();
}
return ;
}