题解：
一道极水的插头$dp$。
根本不需要左右括号分开看，直接都当作括号。
什么三进制四进制，二进制就可做。
讨论比模板要少。
（luogu丧心出题人有hack点。。。）
代码：
#include#include #include using namespace std;#define N 15#define ll long longint T,n,m,k,tx,ty;int a[N][N];ll ans,bas[N];struct Map{ int hed[100050],cnt[2]; struct EG { int nxt; ll to,w; }e[1<<11][2]; void ae(int f,ll t,ll w) { e[++cnt[k]][k].to = t; e[cnt[k]][k].nxt = hed[f]; e[cnt[k]][k].w = w; hed[f] = cnt[k]; } void push(ll u,ll w) { for(int j=hed[u%100000];j;j=e[j][k].nxt) if(e[j][k].to==u) { e[j][k].w+=w; return ; } ae(u%100000,u,w); } void clear() { memset(hed,0,sizeof(hed)); cnt[k] = 0; }}mp;void init(){ k^=1; mp.clear();}void fkctr(){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j])return ; ans++;}int main(){ scanf("%d",&T); bas[0]=1; for(int i=1;i<=11;i++)bas[i]=bas[i-1]<<1; for(int cse=1;cse<=T;cse++) { k = 0;ans = 0; memset(a,0,sizeof(a)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&a[i][j]); if(a[i][j])tx=i,ty=j; } mp.clear(); mp.push(0,1); for(int i=1;i<=n;i++) { for(int j=1;j<=mp.cnt[k];j++)mp.e[j][k].to<<=1; for(int j=1;j<=m;j++) { init(); for(int o=1;o<=mp.cnt[!k];o++) { ll now = mp.e[o][!k].to,val = mp.e[o][!k].w; int lp = (now>>(j-1))&1,rp = (now>>j)&1; if(!a[i][j]) { if(!lp&&!rp) { ll tmp = now; mp.push(tmp,val); } }else { if(!lp&&!rp) { if(a[i+1][j]&&a[i][j+1]) { ll tmp = now+bas[j-1]+bas[j]; mp.push(tmp,val); } }else if(!lp&&rp) { if(a[i][j+1]) { ll tmp = now; mp.push(tmp,val); } if(a[i+1][j]) { ll tmp = now+bas[j-1]-bas[j]; mp.push(tmp,val); } }else if(lp&&!rp) { if(a[i][j+1]) { ll tmp = now-bas[j-1]+bas[j]; mp.push(tmp,val); } if(a[i+1][j]) { ll tmp = now; mp.push(tmp,val); } }else { ll tmp = now-bas[j-1]-bas[j]; mp.push(tmp,val); if(i==tx&&j==ty) ans+=val; } } } } } fkctr(); printf("%lld\n",ans); } return 0;}