题意
一个 \(n\times m\) 的方格纸，有一些格子不能走。给出一个 \(k\) ，求有多少种方案，用 \(k\) 个不相交，不嵌套 的环覆盖所有可以走的格子。\(n,m\le 12\) 。
分析
若只有 \(k\) 个环的限制，那把它放进状态里就可以了。关键是如何解决不嵌套问题。我们在一个环形成的时候处理嵌套。若这个环被奇数个插头套着，那它至少会被它外层的那对插头形成的环包含，所以不转移。若是偶数个，那么接下来继续这样进行，就一定不会发生嵌套的情况。
为什么呢？考虑刚刚形成的这个环，外面的那层线，由于这个环被偶数个插头对套着，所以外层的线是被奇数个插头对套着，所以它一定不能成环，那么就会消除外面的两层。剩下的情况是一样的。
于是讨论一下，转移即可。
复杂度为 \(O(nm|s|)\) 。
这也算是插头dp棋盘模型的一个结束了。
代码
卡掉了所有的内置 hash_table 。终于手写了一次，因为不想改代码，所以实现了大部分接口，除了 map::iterator 不知道怎么实现，不过也不是很需要。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ui;
typedef long long giant;
const int maxn=14;
const int maxs=3e5;
const ui haq=3e5+7;
const int q=1e9+7;
inline int Plus(int x,int y) {return ((giant)x+(giant)y)%q;}
inline void Pe(int &x,int y) {x=Plus(x,y);}
int n,m,ned;
bool no[maxn][maxn];
struct Hash {
struct E {
ui v;
int w,nxt;
} e[maxs];
int h[haq],tot;
inline void clear() {tot=0,memset(h,0,sizeof h);}
Hash () {clear();}
inline int& operator [] (ui x) {
ui wh=x%haq;
for (int i=h[wh];i;i=e[i].nxt) if (e[i].v==x) return e[i].w;
e[++tot]=(E){x,0,h[wh]};
return e[h[wh]=tot].w;
}
};
struct Map {
Hash *hs;
Map () {hs=new Hash();}
inline void clear() {hs->clear();}
inline int& operator [] (ui x) {return (*hs)[x];}
inline void swap(Map &o) {
std::swap(hs,o.hs);
}
} f,g;
void get(Map &g) {
for (int i=1;i<=g.hs->tot;++i) printf("[%llu]: %d, ",g.hs->e[i].v,g.hs->e[i].w);
puts("");
}
int mt[maxn];
inline ui get(ui x,int p) {
if (p==m+2) return x>>((m+2)<<1);
return (x>>(p<<1))&3;
}
inline ui mod(ui x,int p,ui d) {
if (p==m+2) {
ui bef=x&((1u<<((m+2)<<1))-1);
return bef+(d<<((m+2)<<1));
}
return (x&(~(3<<(p<<1))))+(d<<(p<<1));
}
inline void match(ui x,int *mt) {
static int sta[maxn];
int top=0;
for (int i=0;i<maxn;++i) mt[i]=0;
for (int i=1;i<=m+1;++i) {
const ui d=get(x,i);
if (d==1) sta[++top]=i; else if (d==2) {
int p=sta[top--];
mt[p]=i,mt[i]=p;
}
}
}
void dec(ui x) {
for (int j=1;j<=m+1;++j) printf("%llu ",get(x,j));
printf("%llu\n",get(x,m+2));
}
void work() {
scanf("%d%d%d",&n,&m,&ned);
memset(no,0,sizeof no);
for (int i=1;i<=n;++i) {
static char s[maxn];
scanf("%s",s+1);
for (int j=1;j<=m;++j) no[i][j]=(s[j]=='*');
}
if (ned>n*m/4) {
puts("0");
return;
}
f.clear(),g.clear();
f[0]=1;
for (int i=1;i<=n;++i) {
f.swap(g),f.clear();
for (int it=1;it<=g.hs->tot;++it) {
const ui &d=g.hs->e[it].v,s=get(d,m+2);
const int &w=g.hs->e[it].w;
if (get(d,m+1)==0) Pe(f[mod(mod(d,m+2,0)<<2,m+2,s)],w);
}
for (int j=1;j<=m;++j) {
f.swap(g),f.clear();
for (int it=1;it<=g.hs->tot;++it) {
const ui &d=g.hs->e[it].v,s=get(d,m+2),e=mod(mod(d,j,0),j+1,0),x=get(d,j),y=get(d,j+1);
const int &w=g.hs->e[it].w;
match(d,mt);
if (no[i][j]) {
if (x==0 && y==0) Pe(f[d],w);
continue;
}
if (x==0 && y==0) Pe(f[mod(mod(e,j,1),j+1,2)],w); else
if (x==0 || y==0) {
Pe(f[mod(e,j,x+y)],w);
Pe(f[mod(e,j+1,x+y)],w);
} else if (x==1 && y==1) Pe(f[mod(e,mt[j+1],1)],w);
else if (x==2 && y==2) Pe(f[mod(e,mt[j],2)],w);
else if (x==2 && y==1) Pe(f[e],w);
else if (x==1 && y==2) {
if (s>=ned) continue;
int cnt=0;
for (int k=1;k<j;++k) cnt+=(bool)get(d,k);
if (~cnt&1) Pe(f[mod(e,m+2,s+1)],w);
}
}
}
}
printf("%d\n",f[mod(0,m+2,ned)]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
int T;
scanf("%d",&T);
while (T--) work();
return 0;
}