题解：【ABC211E】 Red Polyomino
题目链接
薄纱爆搜老哥。显然是染色模型，我们只需要维护连通性（即每个位置属于哪个连通块），不需要具体维护插头，考虑逐格 DP 维护轮廓线，类似于神秘的生物。恰好染色 \(k\) 个格子很烦，不过 \(k\) 不大，不妨直接放到状态里面，我选择了最小表示法哈希。设 \(f_{i,j,S}\) 表示当前在第 \(i\) 个格子，当前轮廓线状态为 \(S\)，总共染色了 \(j\) 个格子的方案数。第一维依旧是滚动数组优化掉。枚举转移到哪个格子，当前染色了多少和轮廓线的状态，考虑如何转移：
- 当前格子是障碍物
- 若当前格上侧染色了并且当前轮廓线上上侧所属的连通块没有其他露出来的地方，那么就没有机会再使上方这一部分连通起来，所以不能转移。否则就可以将上个状态的值转移过来。
- 当前格子不是障碍物
- 若当前格左侧和上侧都没有选，则既可以选择维持现状、当前格也不选，也可以选择选择当前格，新建一个连通块。
- 若当前格左侧选了，上侧没选，则当前格也可以考虑不选或者延伸左侧连通块。
- 若当前格左侧没选，上侧选了，则当前格可以延申上侧连通块；如果不选的话还是要考虑上侧所属的连通块有没有其他露出来的地方，如果还有就可以不选这个格子。
- 若当前格左侧和上侧都选了，如果选当前格子就会使两个联通块联通，需要手动修改状态；不选当前格子，约束条件和上面相同。
在每个格子转移完之后直接再次枚举状态，如果该状态 \(S\) 只有一个连通块，则直接累加上答案 \(f_{i,k,S}\)。
最多只有四种连通块即五个状态，依然是方便运算直接压八进制，新建一个连通块直接把状态设成 \(7\) 就好了。于是做到 \(\mathcal O(nmkT)\)，其中 \(T\) 是总方案数，毛估估一下也就一千出头，搜出来也确实如此，第三个样例的状态只有 \(1100\)。
#include<bits/stdc++.h>
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define pb pop_back
#define ins insert
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define power(x) ((x)*(x))
#define gcd(x,y) (__gcd((x),(y)))
#define lcm(x,y) ((x)*(y)/gcd((x),(y)))
#define lg(x,y) (__lg((x),(y)))
using namespace std;
namespace FastIO
{
template<typename T=int> inline T read()
{
T s=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
return s*w;
}
template<typename T> inline void read(T &s)
{
s=0; int w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
s=s*w;
}
template<typename T,typename... Args> inline void read(T &x,Args &...args)
{
read(x),read(args...);
}
template<typename T> inline void write(T x,char ch)
{
if(x<0) x=-x,putchar('-');
static char stk[25]; int top=0;
do {stk[top++]=x%10+'0',x/=10;} while(x);
while(top) putchar(stk[--top]);
if(ch!='~') putchar(ch);
return;
}
}
using namespace FastIO;
namespace MTool
{
#define TA template<typename T,typename... Args>
#define TT template<typename T>
static const int Mod=1e9+7;
TT inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
TT inline void cmax(T &a,T b) {a=max(a,b);}
TT inline void cmin(T &a,T b) {a=min(a,b);}
TA inline void cmax(T &a,T b,Args... args) {a=max({a,b,args...});}
TA inline void cmin(T &a,T b,Args... args) {a=min({a,b,args...});}
TT inline void Madd(T &a,T b) {a=a+b>=Mod?a+b-Mod:a+b;}
TT inline void Mdel(T &a,T b) {a=a-b<0?a-b+Mod:a-b;}
TT inline void Mmul(T &a,T b) {a=a*b%Mod;}
TT inline void Mmod(T &a) {a=(a%Mod+Mod)%Mod;}
TT inline T Cadd(T a,T b) {return a+b>=Mod?a+b-Mod:a+b;}
TT inline T Cdel(T a,T b) {return a-b<0?a-b+Mod:a-b;}
TT inline T Cmul(T a,T b) {return a*b%Mod;}
TT inline T Cmod(T a) {return (a%Mod+Mod)%Mod;}
TA inline void Madd(T &a,T b,Args... args) {Madd(a,Cadd(b,args...));}
TA inline void Mdel(T &a,T b,Args... args) {Mdel(a,Cadd(b,args...));}
TA inline void Mmul(T &a,T b,Args... args) {Mmul(a,Cmul(b,args...));}
TA inline T Cadd(T a,T b,Args... args) {return Cadd(Cadd(a,b),args...);}
TA inline T Cdel(T a,T b,Args... args) {return Cdel(Cdel(a,b),args...);}
TA inline T Cmul(T a,T b,Args... args) {return Cmul(Cmul(a,b),args...);}
TT inline T qpow(T a,T b) {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
TT inline T qmul(T a,T b) {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
TT inline T spow(T a,T b) {int res=1; while(b) {if(b&1) res=qmul(res,a); a=qmul(a,a); b>>=1;} return res;}
TT inline void exgcd(T A,T B,T &X,T &Y) {if(!B) return X=1,Y=0,void(); exgcd(B,A%B,Y,X),Y-=X*(A/B);}
TT inline T Ginv(T x) {T A=0,B=0; exgcd(x,Mod,A,B); return Cmod(A);}
#undef TT
#undef TA
}
using namespace MTool;
inline void file()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
return;
}
bool Mbe;
namespace LgxTpre
{
static const int MAX=10;
static const int Max=10000;
static const int inf=2147483647;
static const int INF=4557430888798830399;
int n,m,K,a[MAX][MAX],ans;
int now,last,f[2][MAX][Max];
char c;
namespace Hash
{
namespace MinimumRepresent
{
constexpr int mask=7,offest=3;
int Ment[MAX],Vis[MAX];
inline int GetMin(int s)
{
memset(Vis,-1,sizeof Vis),Vis[0]=0;
int tot=0,ns=0;
for(int i=0;i<m;++i) Ment[i]=s>>(i*offest)&mask;
for(int i=0;i<m;++i) if(!~Vis[Ment[i]]) Vis[Ment[i]]=++tot,Ment[i]=tot; else Ment[i]=Vis[Ment[i]];
for(int i=0;i<m;++i) ns|=Ment[i]<<(i*offest);
return ns;
}
inline int GetTyp(int s)
{
memset(Vis,-1,sizeof Vis),Vis[0]=0;
int tot=0;
for(int i=0;i<m;++i) Ment[i]=s>>(i*offest)&mask;
for(int i=0;i<m;++i) if(!~Vis[Ment[i]]) Vis[Ment[i]]=++tot,Ment[i]=tot; else Ment[i]=Vis[Ment[i]];
return tot;
}
}
using namespace MinimumRepresent;
constexpr int mod=1000003;
int nex[Max],head[mod],content[Max],tot;
inline void ins(int x) {nex[++tot]=head[x%mod],content[tot]=x,head[x%mod]=tot;}
inline int find(int x) {for(int i=head[x%mod];i;i=nex[i]) if(content[i]==x) return i; return ins(x),tot;}
}
using namespace Hash;
inline void lmy_forever()
{
read(n),m=n,read(K);
for(int i=0;i<n;++i) for(int j=0;j<m;++j) {do c=getchar(); while(c!='#'&&c!='.'); a[i][j]=c=='.';}
now=0,last=1,f[now][0][find(0)]=1;
for(int i=0;i<n;++i) for(int j=0;j<m;++j)
{
now^=1,last^=1,memset(f[now],0,sizeof f[now]);
int all=tot;
for(int k=0;k<=K;++k) for(int p=1;p<=all;++p) if(f[last][k][p])
{
auto DO=[&](int S,int V)->void{S=GetMin(S); if(k==K) return; f[now][k+V][find(S)]+=f[last][k][p];};
auto Check=[&](int S,int T)->bool{bool flag=0; for(int u=0;u<m;++u) flag|=(u!=j&&(S>>(u*offest)&mask)==T); return flag;};
int state=content[p],left=j==0?0:state>>((j-1)*offest)&mask,up=state>>(j*offest)&mask;
if(!a[i][j])
{
if(up&&!Check(state,up)) continue;
DO(state^(up<<(j*offest)),0); continue;
}
if(!left&&!up) DO(state,0),DO(state^(7ll<<(j*offest)),1);
else if(left&&!up) DO(state,0),DO(state^(left<<(j*offest)),1);
else if(!left&&up) Check(state,up)?(DO(state,1),DO(state^(up<<(j*offest)),0)):(DO(state,1));
else
{
if(Check(state,up)) DO(state^(up<<(j*offest)),0);
int nstate=state;
for(int u=0;u<m;++u) if((nstate>>(u*offest)&mask)==up) nstate^=(up<<(u*offest))^(left<<(u*offest));
DO(nstate,1);
}
}
for(int p=1;p<=tot;++p) if(f[now][K][p]) if(GetTyp(content[p])==1) ans+=f[now][K][p];
}
write(ans,'\n');
}
}
bool Med;
signed main()
{
// file();
fprintf(stderr,"%.3lf MB\n",abs(&Med-&Mbe)/1048576.0);
int Tbe=clock();
LgxTpre::lmy_forever();
int Ted=clock();
cerr<<1e3*(Ted-Tbe)/CLOCKS_PER_SEC<<" ms\n";
return (0-0);
}