P5056

发表于 分类于
【模板】插头dp

【模板】插头dp

耐心一点，再耐心一点。。。

我们用轮廓线上的插头情况生成括号序列，根据括号序列的合法性判断状态的合法性。

然后连接的时候也会影响括号序列。

我这里采用了一种很深必的方法存状态，就是轮廓线侧边的状态单独用一维，结果造成了很多麻烦，而且导致理论复杂度很差。。。

因为状态巨多，所以不能直接枚举，需要用个数组存着，再用 Hash 判重。

这里我偷懒直接用了 STL map，导致程序只能在开 O2 的情况下才能过。。。

实际上这题最重要的一点就是转移。

窃图

偷懒嫖过来一张图。

因为连接两个相同的括号意味着接口消失，并产生括号的改变，这个可以自己手画个图知道。。。

时间复杂度 $O(nm3^m)$，多带了一个 $\log$ 的大常数（看上去就不太正确）。。。

但是过了所以就不换什么 Hash 之类的了（换成 Hash 复杂度就对了，大概）。。。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
#include<iostream>
#include<cstdio>
#include<map>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

const ll N=12,M=3e5;

ll n,m,ex,ey,ans;
ll a[N+5][N+5],f[2][N+5][M+5][3],vis[2][M+5],cnt[2];
char s[N+5];
map<ll,ll> ff;

inline bool Check(ll x,ll y,ll z) {
  static ll a[N+5];ll cnt=0,top=0;
  for(ll i=1;i<=m;i++,x/=3ll) {a[++cnt]=x%3ll;if(i==y) a[++cnt]=z;}
  for(ll i=1;i<=m+1;i++) {
    if(a[i]==1) top++;if(a[i]==2) top--;if(top<0) return 0;
  }
  return top==0;
}

inline ll Pow(ll b,ll p) {ll r=1;for(;p;b*=b,p>>=1) if(p&1) r*=b;return r;}
inline ll Kch_i(ll s,ll x) {for(ll i=1;i<x;i++) s/=3ll;return s%3ll;}
inline ll Kass_i(ll s,ll x,ll y) {
  ll tmp1=Pow(3ll,x-1);ll tmp2=tmp1*3ll;return s/tmp2*tmp2+s%tmp1+y*tmp1;
}
inline ll Modi(ll x,ll y,ll z) {
  static ll a[N+5],st[N+5],mat[N+5];ll cnt=0,top=0,tmp=x;
  for(ll i=1;i<=m;i++,x/=3ll) {a[++cnt]=x%3ll;if(i==y) a[++cnt]=z;}
  for(ll i=1;i<=m+1;i++) {
    if(a[i]==1) st[++top]=i;
    if(a[i]==2) {mat[i]=st[top];mat[st[top]]=i;top--;}
  }
  if(z==1) return Kass_i(tmp,mat[y+2]-1,1);
  else return Kass_i(tmp,mat[y+1],2);
}

int main() {

  n=read();m=read();
  for(ll i=1;i<=n;i++) {
    scanf("%s",s+1);
    for(ll j=1;j<=m;j++) {
      if(s[j]=='.') {a[i][j]=1;ex=i;ey=j;}
    }
  }

  ll tmp=Pow(3ll,m);
  vis[0][++cnt[0]]=0;f[0][m][1][0]=1;
  for(ll i=1;i<=n;i++) {
    for(ll q=1;q<=cnt[0];q++) {
      ll p=vis[0][q];
      // printf("i=%lld j=%lld p=%lld\n",i,1ll,p);
      if(!Check(p,m,0)) continue;
      ll tmp1=Kch_i(p,1),tmp2;
      if(tmp1==0) {
        if(a[i][1]) {
          tmp2=Kass_i(p,1,1);
          if(ff.find(tmp2)==ff.end()) {
            vis[1][++cnt[1]]=tmp2;ff[tmp2]=cnt[1];
          }
          f[i&1][1][ff[tmp2]][2]+=f[(i-1)&1][m][q][0];
        }
        else {
          if(ff.find(p)==ff.end()) {
            vis[1][++cnt[1]]=p;ff[p]=cnt[1];
          }
          f[i&1][1][ff[p]][0]+=f[(i-1)&1][m][q][0];
        }
      }
      if(tmp1==1) {
        if(a[i][1]) {
          tmp2=Kass_i(p,1,0);
          if(ff.find(tmp2)==ff.end()) {
            vis[1][++cnt[1]]=tmp2;ff[tmp2]=cnt[1];
          }
          f[i&1][1][ff[tmp2]][1]+=f[(i-1)&1][m][q][0];
          if(ff.find(p)==ff.end()) {
            vis[1][++cnt[1]]=p;ff[p]=cnt[1];
          }
          f[i&1][1][ff[p]][0]+=f[(i-1)&1][m][q][0];
        }
      }
      if(tmp1==2) {
        if(a[i][1]) {
          tmp2=Kass_i(p,1,0);
          if(ff.find(tmp2)==ff.end()) {
            vis[1][++cnt[1]]=tmp2;ff[tmp2]=cnt[1];
          }
          f[i&1][1][ff[tmp2]][2]+=f[(i-1)&1][m][q][0];
          if(ff.find(p)==ff.end()) {
            vis[1][++cnt[1]]=p;ff[p]=cnt[1];
          }
          f[i&1][1][ff[p]][0]+=f[(i-1)&1][m][q][0];
        }
      }
    }
    ff.clear();cnt[0]=0;
    for(ll j=2;j<=m;j++) {
      for(ll q=1;q<=cnt[(j-1)&1];q++) {
        ll p=vis[(j-1)&1][q];
        // printf("i=%lld j=%lld p=%lld\n",i,j,p);
        ll tmp1=Kch_i(p,j),tmp2;
        if(tmp1==0) {
          if(a[i][j]) {
            if(Check(p,j-1,0)) {
              tmp2=Kass_i(p,j,1);
              if(ff.find(tmp2)==ff.end()) {
                vis[j&1][++cnt[j&1]]=tmp2;ff[tmp2]=cnt[j&1];
              }
              f[i&1][j][ff[tmp2]][2]+=f[i&1][j-1][q][0];
            }
            if(Check(p,j-1,1)) {
              tmp2=Kass_i(p,j,1);
              if(ff.find(tmp2)==ff.end()) {
                vis[j&1][++cnt[j&1]]=tmp2;ff[tmp2]=cnt[j&1];
              }
              f[i&1][j][ff[tmp2]][0]+=f[i&1][j-1][q][1];
              if(ff.find(p)==ff.end()) {
                vis[j&1][++cnt[j&1]]=p;ff[p]=cnt[j&1];
              }
              f[i&1][j][ff[p]][1]+=f[i&1][j-1][q][1];
            }
            if(Check(p,j-1,2)) {
              tmp2=Kass_i(p,j,2);
              if(ff.find(tmp2)==ff.end()) {
                vis[j&1][++cnt[j&1]]=tmp2;ff[tmp2]=cnt[j&1];
              }
              f[i&1][j][ff[tmp2]][0]+=f[i&1][j-1][q][2];
              if(ff.find(p)==ff.end()) {
                vis[j&1][++cnt[j&1]]=p;ff[p]=cnt[j&1];
              }
              f[i&1][j][ff[p]][2]+=f[i&1][j-1][q][2];
            }
          }
          else {
            if(Check(p,j-1,0)) {
              if(ff.find(p)==ff.end()) {
                vis[j&1][++cnt[j&1]]=p;ff[p]=cnt[j&1];
              }
              f[i&1][j][ff[p]][0]+=f[i&1][j-1][q][0];
            }
          }
        }
        if(tmp1==1) {
          if(a[i][j]) {
            if(Check(p,j-1,0)) {
              tmp2=Kass_i(p,j,0);
              if(ff.find(tmp2)==ff.end()) {
                vis[j&1][++cnt[j&1]]=tmp2;ff[tmp2]=cnt[j&1];
              }
              f[i&1][j][ff[tmp2]][1]+=f[i&1][j-1][q][0];
              if(ff.find(p)==ff.end()) {
                vis[j&1][++cnt[j&1]]=p;ff[p]=cnt[j&1];
              }
              f[i&1][j][ff[p]][0]+=f[i&1][j-1][q][0];
            }
            if(Check(p,j-1,1)) {
              tmp2=Modi(p,j-1,1);tmp2=Kass_i(tmp2,j,0);
              if(ff.find(tmp2)==ff.end()) {
                vis[j&1][++cnt[j&1]]=tmp2;ff[tmp2]=cnt[j&1];
              }
              f[i&1][j][ff[tmp2]][0]+=f[i&1][j-1][q][1];
            }
            if(Check(p,j-1,2)) {
              tmp2=Kass_i(p,j,0);
              if(ff.find(tmp2)==ff.end()) {
                vis[j&1][++cnt[j&1]]=tmp2;ff[tmp2]=cnt[j&1];
              }
              f[i&1][j][ff[tmp2]][0]+=f[i&1][j-1][q][2];
            }
          }
        }
        if(tmp1==2) {
          if(a[i][j]) {
            if(Check(p,j-1,0)) {
              tmp2=Kass_i(p,j,0);
              if(ff.find(tmp2)==ff.end()) {
                vis[j&1][++cnt[j&1]]=tmp2;ff[tmp2]=cnt[j&1];
              }
              f[i&1][j][ff[tmp2]][2]+=f[i&1][j-1][q][0];
              if(ff.find(p)==ff.end()) {
                vis[j&1][++cnt[j&1]]=p;ff[p]=cnt[j&1];
              }
              f[i&1][j][ff[p]][0]+=f[i&1][j-1][q][0];
            }
            if(Check(p,j-1,1)&&i==ex&&j==ey) {
              tmp2=Kass_i(p,j,0);
              if(ff.find(tmp2)==ff.end()) {
                vis[j&1][++cnt[j&1]]=tmp2;ff[tmp2]=cnt[j&1];
              }
              f[i&1][j][ff[tmp2]][0]+=f[i&1][j-1][q][1];
              if(tmp2==0) ans=f[i&1][j][ff[tmp2]][0];
            }
            if(Check(p,j-1,2)) {
              tmp2=Modi(p,j-1,2);tmp2=Kass_i(tmp2,j,0);
              if(ff.find(tmp2)==ff.end()) {
                vis[j&1][++cnt[j&1]]=tmp2;ff[tmp2]=cnt[j&1];
              }
              f[i&1][j][ff[tmp2]][0]+=f[i&1][j-1][q][2];
            }
          }
        }
      }
      ff.clear();cnt[(j-1)&1]=0;
    }
    if(m&1) {
      cnt[0]=cnt[1];cnt[1]=0;
      for(ll j=1;j<=cnt[0];j++) {vis[0][j]=vis[1][j];}
    }
    for(ll j=1;j<=m;j++) {
      for(ll p=0;p<M;p++) {
        f[(i-1)&1][j][p][0]=f[(i-1)&1][j][p][1]=f[(i-1)&1][j][p][2]=0;
      }
    }
  }

  write(ans);

  return 0;
}