P3272

发表于 更新于 分类于
[SCOI2011]地板

[SCOI2011]地板

仍然是比较弱的插头 DP。。。

不过分类讨论已经有够麻烦的了。。。

可能有人觉得这个状态不太好搞，因为这个状态要保证每个地毯只拐一次，每个地毯还必须有拐。

我们定义红（1）和黑（2）两种插头，分别表示没有拐过和拐过，用 0 表示没有插头伸出。

然后我们的插头类型大概就是这么几种：

插头种类

然后这个箭头表示会往指向的格子产生一个插头，然后那个格子必须要接上这个箭头才能转移。如果没有产生插头，对于该格子来说与 0 是等价的。

要知道的是，1 类插头可以接 2 类插头中带拐的（比如 2 中第四、五和七）；而 2 类只能接 2 类中不带拐的（并且 2 类才可以接终止插头）。

L 形一共分成四类，每一类的组成如上。

然后就是巨大多分类讨论，和一般的插头 DP 就没什么区别了。。。

每个讨论的格式基本都是：

  1. 该格子的头上是什么插头。

  2. 知道了头上的插头情况，讨论左侧插头情况，看这个格子能塞什么插头。

  3. 根据所塞插头的情况转移。

定义状态 $f(i,j,s,k)$，其中 $s$ 是一个三进制数，表示轮廓线上向下的插头情况，$k$ 是轮廓线侧向的插头情况。

时间复杂度 $O(nm3^m)$（$m$ 取 $\min\{n,m\}$，可以通过顺时针旋转整个网格来达到优化）。

代码：

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
#include<iostream>
#include<cstdio>
#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 L=10,N=1e2,M=6e5,mo=20110520;

ll n,m;
ll a[N+5][N+5],f[2][L+5][M+5][3];
char s[N+5][N+5];

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;
}

int main() {

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

  ll tmp=Pow(3ll,m);f[0][m][0][0]=1;
  for(ll i=1;i<=n;i++) {
    for(ll p=0;p<tmp;p++) {
      ll tmp1=Kch_i(p,1),tmp2;
      if(tmp1==0) {
        if(a[i][1]) {
          tmp2=Kass_i(p,1,2);
          f[i&1][1][tmp2][2]=(f[i&1][1][tmp2][2]+f[(i-1)&1][m][p][0])%mo;
          tmp2=Kass_i(p,1,1);
          f[i&1][1][tmp2][0]=(f[i&1][1][tmp2][0]+f[(i-1)&1][m][p][0])%mo;
          f[i&1][1][p][1]=(f[i&1][1][p][1]+f[(i-1)&1][m][p][0])%mo;
        }
        else {
          f[i&1][1][p][0]=(f[i&1][1][p][0]+f[(i-1)&1][m][p][0])%mo;
        }
      }
      if(tmp1==1) {
        if(a[i][1]) {
          tmp2=Kass_i(p,1,0);
          f[i&1][1][tmp2][2]=(f[i&1][1][tmp2][2]+f[(i-1)&1][m][p][0])%mo;
          f[i&1][1][p][0]=(f[i&1][1][p][0]+f[(i-1)&1][m][p][0])%mo;
        }
      }
      if(tmp1==2) {
        if(a[i][1]) {
          tmp2=Kass_i(p,1,0);
          f[i&1][1][tmp2][0]=(f[i&1][1][tmp2][0]+f[(i-1)&1][m][p][0])%mo;
          f[i&1][1][p][0]=(f[i&1][1][p][0]+f[(i-1)&1][m][p][0])%mo;
        }
      }
    }
    for(ll j=2;j<=m;j++) {
      for(ll p=0;p<tmp;p++) {
        ll tmp1=Kch_i(p,j),tmp2;
        if(tmp1==0) {
          if(a[i][j]) {
            tmp2=Kass_i(p,j,1);
            f[i&1][j][tmp2][0]=(f[i&1][j][tmp2][0]+f[i&1][j-1][p][0])%mo;
            tmp2=Kass_i(p,j,2);
            f[i&1][j][tmp2][0]=(f[i&1][j][tmp2][0]+f[i&1][j-1][p][1])%mo;
            f[i&1][j][tmp2][2]=(f[i&1][j][tmp2][2]+f[i&1][j-1][p][0])%mo;
            f[i&1][j][p][0]=(f[i&1][j][p][0]+f[i&1][j-1][p][2])%mo;
            f[i&1][j][p][1]=(f[i&1][j][p][1]
            +f[i&1][j-1][p][1]+f[i&1][j-1][p][0])%mo;
            f[i&1][j][p][2]=(f[i&1][j][p][2]+f[i&1][j-1][p][2])%mo;
          }
          else {
            f[i&1][j][p][0]=(f[i&1][j][p][0]+f[i&1][j-1][p][0])%mo;
          }
        }
        if(tmp1==1) {
          if(a[i][j]) {
            tmp2=Kass_i(p,j,0);
            f[i&1][j][tmp2][0]=(f[i&1][j][tmp2][0]+f[i&1][j-1][p][1])%mo;
            f[i&1][j][tmp2][2]=(f[i&1][j][tmp2][2]+f[i&1][j-1][p][0])%mo;
            f[i&1][j][p][0]=(f[i&1][j][p][0]+f[i&1][j-1][p][0])%mo;
          }
        }
        if(tmp1==2) {
          if(a[i][j]) {
            tmp2=Kass_i(p,j,0);
            f[i&1][j][tmp2][0]=(f[i&1][j][tmp2][0]+f[i&1][j-1][p][0])%mo;
            f[i&1][j][p][0]=(f[i&1][j][p][0]+f[i&1][j-1][p][0])%mo;
          }
        }
      }
    }
    for(ll j=1;j<=m;j++) {
      for(ll p=0;p<tmp;p++) {
        f[(i-1)&1][j][p][0]=f[(i-1)&1][j][p][1]=f[(i-1)&1][j][p][2]=0;
      }
    }
  }

  write(f[n&1][m][0][0]);

  return 0;
}